Embedding Graphs in Cylinder and Torus Books

Abstract

In the classical book embedding problem, a $k$-book is defined to be a line $L$ in $3$-space (the spine) together with $k$ half-planes (the pages) joined together at $L$. We introduce two variations on the classical book in which edges are allowed to wrap in either one or two directions. The first is a cylindrical book where the spine is a line $L$ in $3$-space and the pages are nested cylindrical shells joined together at $L$. The second is a torus book where the spine is the inner equator of a torus and the pages are nested torus shells joined together at this equator. We give optimal edge bounds for embeddings of finite simple graphs in cylinder and torus books and give best-possible embeddings of $K_n$ in torus books. We also compare both books with the classical book.