Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

1987/01/01 by Fan Chung, Frank Thomson Leighton, Arnold L. Rosenberg · 12 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #graph theory and CDMA systems #Embedding #Combinatorics #Book embedding #Mathematics #Vertex (graph theory) #Mathematical proof #Discrete mathematics #Very-large-scale integration #Graph embedding #Graph #Pathwidth #Line graph #Computer science #Geometry #Artificial intelligence

paper · doi:10.1137/0608002

openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We study the graph-theoretic problem of embedding a graph in a book with its vertices in a line along the spine of the book and its edges on the pages in such a way that edges residing on the same page do not cross. This problem abstracts layout problems arising in the routing of multilayer printed circuit boards and in the design of fault-tolerant processor arrays. In devising an embedding, one strives to minimize both the number of pages used and the “cutwidth” of the edges on each page. Our main results (1) present optimal embeddings of a variety of families of graphs; (2) exhibit situations where one can achieve small pagenumber only at the expense of large cutwidth; and (3) establish bounds on the minimum pagenumber of a graph based on various structural properties of the graph. Notable in the last category are proofs that (a) every n-vertex d-valent graph can be embedded using O( dn^{1/ 2} ) pages, and (b) for every d > 2 and all large n, there are n-vertex d-valent graphs whose pagenumber is at least Ω ( \fracn^{1/ 2 - 1/d}log² n ).

Citations

• Characterizations of outerplanar graphs
• The book thickness of a graph
• The Complexity of Coloring Circular Arcs and Chords
• Die Theorie der regulären graphs

Cited by

• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• On the page number of RNA secondary structures with pseudoknots
• On the Pagenumber of the Cube-Connected Cycles
• Stack-Number is Not Bounded by Queue-Number
• RNA Structures with Pseudo-knots: Graph-theoretical, Combinatorial, and Statistical Properties
• Crossing minimization in linear embeddings of graphs
• The pagenumber of k-trees is O(k)
• Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing
• The pagewidth of trivalent planar graphs
• Book embeddings and crossing numbers
• Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages
• Book embedding [wikipedia]