1999/01/01 by Hikoe Enomoto, Miki Miyauchi · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #graph theory and CDMA systems #Advanced Graph Theory Research #Combinatorics #Embedding #Book embedding #Mathematics #Upper and lower bounds #Graph #Enhanced Data Rates for GSM Evolution #Omega #Discrete mathematics #Line graph #Computer science #1-planar graph #Physics #Artificial intelligence
paper · doi:10.1137/s0895480195280319
openalex publication_date 1999/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
This paper studies the problem of embedding a graph G into a book with vertices on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. When each edge is allowed to appear in one or more pages by crossing the spine, one of the authors showed that there exists a three page book embedding of G in which each edge crosses the spine at most O(n) times, where n is the number of vertices. This paper improves the result and shows that there exists a three page book embedding of G in which each edge crosses the spine at most O(log n) times. An Ω(n2) lower bound on the number of crossings of edges over the spine in any book embedding of the complete graph Kn is also shown.