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

Kenta Ozeki
National Institute of Informatics / JST, ERATO, Kawarabayashi Large Graph Project

Atsuhiro Nakamoto
Yokohama National University

Takayuki Nozawa
Yokohama National University



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