Book-embeddings of graphs on the projective plane or the torus

Minisymposium: GRAPH IMBEDDINGS AND MAP SYMMETRIES

Content: A {\em book embedding\/} of a graph $G$ is to put the vertices along the {\em spine\/} (a segment) and each edge of $G$ on a single {\em page\/} (a half-plane with the spine as its boundary) so that no two edges intersect transversely in the same page. We say that a graph $G$ is {\em $k$-page embeddable\/} if $G$ has a book embedding with at most $k$ pages. The {\em pagenumber\/} (or sometimes called {\em stack number} or {\em book thickness}) of a graph $G$ is the minimum of $k$ such that $G$ is $k$-page embeddable. Yannakakis obtained the sharp upper bound: every planar graph has the pagenumber at most four. Then it is natural to ask what about graphs on other surfaces. Nakamoto and Nozawa proved that every graph on the projective plane or on the torus is $9$-page embeddable, and Endo proved that every graph on the torus is $7$-page embeddable. In this talk, we improve those results.

Back to all abstracts