
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.

Topological Book Embedding of Bipartite Graphs
Miki MIYAUCHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E89A
No.5
pp.12231226 Publication Date: 2006/05/01
Online ISSN: 17451337 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: bipartite graph, book embedding, crossings of edges over the spine, pagenumber,
Full Text: PDF(157KB) >>Buy this Article
Summary:
A topological book embedding of a graph is an embedding in a book that carries the vertices in the spine of the book and the edges in the pages so that edges are allowed to cross the spine. Recently, the author has shown that for an arbitrary graph G with n vertices there exists a d+1page book embedding of G in which each edge crosses the spine log_{d }n times. This paper improves the result for the case of bipartite graphs and shows that there exists a d+1page book embedding of a bipartite graph G_{n1,n2} having two partite sets with n_{1} and n_{2} vertices respectively (n_{1} ≥ n_{2}) in which each edge crosses the spine log_{d} n_{2} 1 times.

