Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer SciencesVol.E88-ANo.5pp.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>>
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 logdn times.