Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs

Miki Shimabara MIYAUCHI

Summary :

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 book embedding of G in which each edge crosses the spine O(log₂ 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 paper 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 Ω(n² 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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.8 pp.1732-1734
• Publication Date: 2000/08/25
• Type of Manuscript: LETTER
• Category: Graphs and Networks

Authors

Miki Shimabara MIYAUCHI

Keyword

graphs,  book embedding,  crossings of edges over the spine,  page-number