Embedding planar graphs in four pages (Q1120582)

A book embedding of a graph is an embedding of the vertices along the spine of a ``book'' (i.e., a linear ordering of the vertices) together with an embedding of its edges on the pages so that edges placed in the same page do not intersect. The author proves that any planar graph has a book embedding with at most four pages. The proof is constructive. Moreover, a linear time algorithm is presented for finding such an embedding. In another paper of the author (which is in preparation), examples of planar graphs are constructed which do not admit a book embedding with 3 pages.