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

Miki Shimabara MIYAUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E83-A    No.8    pp.1732-1734
Publication Date: 2000/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
Keyword: 
graphs,  book embedding,  crossings of edges over the spine,  page-number,  

Full Text: PDF>>
Buy this Article


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(log2 n) times. This paper considers a book with more than three pages. In this case, it is known that a complete graph Kn 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(logd n) times. As a direct corollary, for any real number s, there is an ns -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 Kn into a d-page book, there must exist Ω(n2 logd n) points at which edges cross over the spine. This means our result is the best possible for Kn in this case.