# Upper bound on the genus of a k-page graph

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?

-
Here is the refference for book embeddings en.wikipedia.org/wiki/Book_embedding –  Dmitri Jan 17 '10 at 11:48

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.