Embedding a Graph into a d + 1-page Book with m logd n Edge-crossings over the Spine
Miki Shimabara Miyauchi · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2005
A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine ⌈log n⌉ times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine ⌈logdn⌉ times.