Embedding a Graph into a d + 1-page Book with m logd n Edge-crossings over the Spine

Miki MIYAUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E88-A   No.5   pp.1136-1139
Publication Date: 2005/05/01
Online ISSN: 
DOI: 10.1093/ietfec/e88-a.5.1136
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
graph theory,  book embedding,  crossings over the spine,  

Full Text: PDF>>
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; edges are allowed to cross the spine. Enomoto showed that for any graph G having n vertices, there exists a three-page book embedding of G in which each edge crosses the spine log n times. This paper generalizes the result and shows that for any graph G having n vertices, there exists a d + 1-page book embedding of G in which each edge crosses the spine logd n times.