Embedding Outerplanar Graphs in Small Books

DOI10.1137/0608018zbMath0609.05034OpenAlexW2008003769WikidataQ56689181 ScholiaQ56689181MaRDI QIDQ3749074

Lenwood S. Heath

Publication date: 1987

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0608018

zbMATH Keywords

bookalgorithmwidthbook embeddingspineouterplanar graphpagesVLSI processorspagewidth of the embeddingpagewidth of the graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)

Related Items (9)

Two-page book embedding of trees under vertex-neighborhood constraints ⋮ A trade-off between page number and page width of book embeddings of graphs ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ The pagenumber of the class of bandwidth-k graphs is \(k-1\) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The pagewidth of trivalent planar graphs ⋮ On the design of efficient ATM routing schemes ⋮ Recognizing DAGs with page-number 2 is NP-complete

Cites Work

• Finding small simple cycle separators for 2-connected planar graphs
• The book thickness of a graph
• Characterizations of outerplanar graphs
• A Separator Theorem for Planar Graphs
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• The Complexity of Coloring Circular Arcs and Chords
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

This page was built for publication: Embedding Outerplanar Graphs in Small Books