Embedding Outerplanar Graphs in Small Books

DOI10.1137/0608018MaRDI QIDQ3749074zbMATH OpenOpenAlexWikidataFDO

Authors 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

algorithmbookbook embeddingouterplanar graphpagespagewidth of the embeddingpagewidth of the graphspineVLSI processorswidth

Mathematics Subject Classification ID

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

Recommendations

• Book embeddings of nonplanar graphs with small faces in few pages
• Book embedding of projective-planar graphs
• A survey on book-embedding of planar graphs
• A survey on book-embedding of planar graphs
• Optimum embedding of complete graphs in books
• scientific article; zbMATH DE number 1094182
• Book embeddings of regular graphs
• Book embedding of graphs on the projective plane
• Book embedding of locally planar graphs on orientable surfaces
• scientific article; zbMATH DE number 6902663

Cites work

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

Cited in

(20)

• Graphs with small book thickness
• A trade-off between page number and page width of book embeddings of graphs
• The pagewidth of trivalent planar graphs
• On exteriority notions in book embeddings and treewidth
• Two-page book embedding of trees under vertex-neighborhood constraints
• Book embedding of locally planar graphs on orientable surfaces
• Recognizing DAGs with page-number 2 is NP-complete
• scientific article; zbMATH DE number 3914339 (Why is no real title available?)
• scientific article; zbMATH DE number 4002118 (Why is no real title available?)
• Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages
• 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
• Vertex Types in Book-Embeddings
• Triconnected planar graphs of maximum degree five are subhamiltonian
• The subgraph testing model
• On the design of efficient ATM routing schemes
• Recognizing DAGs with page-number 2 is NP-complete
• The pagenumber of the class of bandwidth-k graphs is k-1
• A tight subexponential-time algorithm for two-page book embedding
• Linear layouts revisited: stacks, queues, and exact algorithms

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

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