Embedding graphs into a three page book with O(M log N) crossings of edgesover the spine

This paper studies the problem of embedding a graph G into a book with vert ices 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 o ne or more pages by crossing the spine, one of the authors showed that ther e exists a three page book embedding of G in which each edge crosses the sp ine at most O(n) times, where n is the number of vertices. This paper impro ves 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 boo k embedding of the complete graph K-n is also shown.