Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
Here is the refference for book embeddings en.wikipedia.org/wiki/Book_embedding –  Dmitri Jan 17 '10 at 11:48

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.