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

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