Sparse Graphic Degree Sequences Have Planar Realizations

ABSTRACT A sequence of positive integers is graphic if it is the degree sequence of some simple graph , and planaric if it is the degree sequence of some simple planar graph . It is known that if , then has a realization by a forest, hence it is trivially planaric. This condition for to be realized by a forest is tight, since clearly must be even, and it is known that if then does not have a forest realization. In this paper, we seek bounds on that guarantee that if is graphic then it is also planaric. We show that this holds true when , where is the number of 1's in . Conversely, we show that there are graphic sequences with that are non‐planaric. For the case , we show that is planaric when . Conversely, we show that there is a graphic sequence with that is non‐planaric. In fact, when can be realized by a graph with a 2‐page book embedding.