Embedding Graphs in the Plane—Algorithmic Aspects

DOI10.1016/S0167-5060(08)70719-2MaRDI QIDQ3897065zbMATH OpenOpenAlexFDO

Authors S. Gill Williamson

Publication date 1980

Published in Combinatorial Mathematics, Optimal Designs and Their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-5060(08)70719-2

zbMATH Keywords

linear time algorithmplanar graphsegment graphs of a graph

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited in

(18)

• A characterization of planar graphs by Trémaux orders
• Projective plan and Möbius band obstructions
• A large set of torus obstructions and how they were discovered
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• Gap strings and spanning forests for bridge graphs of biconnected graphs
• Orthogonal drawings of graphs for the automation of VLSI circuit design
• Elimination of local bridges
• Discrete characterizations of planarity part I: the classical viewpoint
• Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs
• Determining outerplanarity using segment graphs
• Finding triconnected components of graphs
• Ranking and unranking planar embeddings
• Menus of kuratowski subgraphs
• Obstructions for the Disk and the Cylinder Embedding Extension Problems
• A matrix analysis of carrier posets of biconnected graphs
• Bijective comparison of optimal planarity algorithms
• Embedding graphs in the torus in linear time
• scientific article; zbMATH DE number 2192203 (Why is no real title available?)

This page was built for publication: Embedding Graphs in the Plane—Algorithmic Aspects

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