Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
Hikoe Enomoto, Miki Shimabara Miyauchi · SIAM Journal on Discrete Mathematics · 1999
This paper studies the problem of embedding a graph G into a book with vertices on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. When each edge is allowed to appear in one or more pages by crossing the spine, one of the authors showed that there exists a three page book embedding of G in which each edge crosses the spine at most O(n) times, where n is the number of vertices. This paper improves the result and shows that there exists a three page book embedding of G in which each edge crosses the spine at most O(log n) times. An $\Omega(n^2)$ lower bound on the number of crossings of edges over the spine in any book embedding of the complete graph Kn is also shown.