17
$\begingroup$

The Erdős–Gallai theorem characterizes which degree sequences are graphical (i.e. realizable by a simple graph).

There has been some work on which degree sequences are planar graphical (i.e. realizable by a simple planar graph). See, for example, On Planar Graphical Degree Sequences by Schmeichel and Hakimi (1977).

What is currently known about which degree sequences are planar graphical?

$\endgroup$

1 Answer 1

12
$\begingroup$

It is always difficult to say what is "currently known," but at least around 2008, the paper

"A Characterization of the degree sequences of 2-trees." Prosenjit Bose, Vida Dujmovi, Danny Krizanc, Stefan Langerman, Pat Morin, David R. Wood, Stefanie Wuhrer. Journal of Graph Theory Volume 58, Issue 3, pages 191–209, July 2008. (journal link)

gives a pretty definitive summary of the state of the art:

That a sequence of $n$ positive integers is the degree sequence of a tree if and only if it sums to $2n − 2$ is a folklore result. Other graph families with known degree sequence characterizations include split graphs [14, 20], $C_4$-minor free graphs [21], unicyclic graphs [1], cacti graphs [15], Halin graphs [2], and edge-maximal outerplanar graphs [18]. The most investigated class of graphs is that of planar graphs. Despite the effort, no characterization of the degree sequences of planar graphs is known, even for edge-maximal planar graphs. Partial results are obtained in [5, 13, 11, 16].

And, obviously, that paper characterizes 2-trees.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .