For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs
Miki Shimabara MIYAUCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/08/25
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Graphs and Networks
graphs, book embedding, crossings of edges over the spine, page-number,
Full Text: PDF>>
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.