MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Here is the refference for book embeddings – Dmitri Jan 17 '10 at 11:48
up vote 3 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.