Optimum embedding of complete graphs in books

DOI10.1016/S0012-365X(97)00131-3MaRDI QIDQ1379820zbMATH OpenFDO

Authors Tomasz Bilski

Publication date 4 May 1999

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(97)00131-3

zbMATH Keywords

bookcomplete graphembedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Review text

The author gives an embedding of the complete graph with \(n\) vertices in a book of width \(n-3\) and \(\lceil n/2 \rceil\) pages---this improves an older result that needs width \(n\) for the same number of pages. An embedding of a graph in a book is an arrangement of the vertices along the spine and edges on the pages such that no edges residing on the same page cross. The width of the embedding is the maximum number of edges that cross any line perpendicular to the spine of the book on any page.

Recommendations

• A trade-off between page number and page width of book embeddings of graphs
• scientific article; zbMATH DE number 4185630
• Embedding planar graphs in four pages
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine

Cites work

• A framework for solving VLSI graph layout problems
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Single Row Routing
• Sorting Using Networks of Queues and Stacks
• The book thickness of a graph

Cited in

(20)

• Improved book-embeddings of incomplete hypercubes
• Embedding connected double-loop networks with even cardinality in books
• Embedding the incomplete hypercube in books
• A trade-off between page number and page width of book embeddings of graphs
• Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis
• A survey on book-embedding of planar graphs
• Embedding planar 5-graphs in three pages
• Book embeddability of series-parallel digraphs
• Embedding generalized Petersen graph in books
• scientific article; zbMATH DE number 3914339 (Why is no real title available?)
• Embedding Outerplanar Graphs in Small Books
• On the page number of complete odd-partite graphs
• scientific article; zbMATH DE number 1094182 (Why is no real title available?)
• scientific article; zbMATH DE number 6902663 (Why is no real title available?)
• Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• scientific article; zbMATH DE number 4185630 (Why is no real title available?)
• On the pagenumber of 1-planar graphs

This page was built for publication: Optimum embedding of complete graphs in books

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1379820)