
For FullText 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 EdgeCrossings on the Spine of Book Embeddings of Graphs
Miki Shimabara MIYAUCHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.8
pp.17321734 Publication Date: 2000/08/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: LETTER Category: Graphs and Networks Keyword: graphs, book embedding, crossings of edges over the spine, pagenumber,
Full Text: PDF>>
Summary:
This paper studies the problem of bookembeddings 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 3page book. Recently, it has been shown that there exists a 3page book 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 edgecrossings on the spine. Thus it becomes an interesting problem to devise bookembeddings of G so as to reduce both the number of pages used and the number of edgecrossings over the spine. This paper shows that there exists a dpage 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, EnomotoMiyauchiOta show that for an integer d, if n is sufficiently large compared with d, then for any embedding of K_{n} into a dpage book, there must exist Ω(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.


