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