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?



Upper bound on the genus of a k-page graph
Every $n$-vertex genus-$g$ graph has at most $3n + 6g - 6$ edges, by Euler's formula. Now consider the three-page graph in which $n-3$ 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 $(n-4)+3(n-3)=4n-13$ 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](http://doi.ieeecomputersociety.org/10.1109/SFCS.1988.21962).


