The pagewidth of trivalent planar graphs

DOI10.1016/0012-365X(91)90398-LMaRDI QIDQ2276971zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Elena Stöhr

Publication date 1991

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(91)90398-l

zbMATH Keywords

book imbeddingfault- tolerant VLSI designpagewidthtrivalent n-vertex planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

A book imbedding of a graph is an ordering of the vertices along the spine of a book (the intersection line of the pages) and an imbedding of the edges on the pages (each edge on one page). The pagewidth of a book imbedding is the maximum number of edges crossing any perpendicular to the spline of the book, over all pages. The author shows that there exist trivalent n-vertex planar graphs G(n) having the property that every 2- page imbedding of G(n) has pagewidth \(\omega\) (n). The result demonstrates that, in some cases, small pagenumber can be achieved only at the expense of large pagewidth. This has relevance to fault-tolerant VLSI design.

Recommendations

• Embedding Outerplanar Graphs in Small Books
• scientific article; zbMATH DE number 3914339
• Embedding planar graphs in four pages
• A survey on book-embedding of planar graphs
• The pagenumber of genus g graphs is O( g )

Cites work

• A trade-off between page number and page width of book embeddings of graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding Outerplanar Graphs in Small Books
• scientific article; zbMATH DE number 3959290 (Why is no real title available?)
• The book thickness of a graph

Cited in

(4)

• On the pagenumber of trivalent Cayley graphs
• The parameterized complexity of extending stack layouts
• Linear layouts revisited: stacks, queues, and exact algorithms
• The parameterized complexity of extending stack layouts

This page was built for publication: The pagewidth of trivalent planar graphs

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