Is there an upper bound on the genus of a graph that has a book embedding on say k pages, or can the genus be arbitrarily large? If not a general bound is known, what happens for k=3?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Every $n$vertex genus$g$ graph has at most $3n + 6g  6$ edges, by Euler's formula. Now consider the threepage graph in which $n3$ vertices are connected in a path (in one of the pages, it doesn't matter which one), followed by three vertices that are each connected (in separate pages) to everything in the path. It has $(n4)+3(n3)=4n13$ edges, so as $n$ grows its genus must be unbounded, and grows linearly in the number of vertices. In the other direction, a graph with genus g must have bounded pagenumber $O(\sqrt g)$; see Malitz, FOCS 1988, doi:10.1109/SFCS.1988.21962. 

