Trade off between page number and number of edge-crossings on the spine of book embeddings of graphs
This paper studies the problem of book-embeddings of graphs. When each edge is allowed to appear in one or more pages by crossing the spine of a book, it is well known that every graph G can be embedded in a 3-page book. Recently, it has been shown that there exists a 3-page hook embedding of G in which each edge crosses the spine O(log(2) n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph K-n with n vertices can be embedded in a [n/2]-page book without any edge-crossings on the spine. Thus it becomes an interesting problem to devise book-embeddings of G so as to reduce both the number of pages used and the number of edge-crossings over the spine. This pager shows that there exists a d-page book embedding of G in which each edge crosses the spine O(log(d) n) times. As a direct corollary for any real number s, there is an [n(s)]-page book embedding of G in which each edge crosses the spine a constant number of times. In another paper, Enomoto-Miyauchi-Ota show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K-n into a d-page book, there must exist Omega(n(2) log(d) n) points at which edges cross over the spine. This means our result is the best possible for K-n in this case.
book embedding graphs crossings of edges over the spine page-number