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
PDF
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.