Embedding Graphs in the Plane—Algorithmic Aspects

DOI10.1016/S0167-5060(08)70719-2zbMath0451.05021OpenAlexW2135513198MaRDI QIDQ3897065

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)

Related Items

Unnamed Item, The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs, Unnamed Item, Ranking and unranking planar embeddings, Bijective comparison of optimal planarity algorithms, Gap strings and spanning forests for bridge graphs of biconnected graphs, Projective plan and Möbius band obstructions, Obstructions for the Disk and the Cylinder Embedding Extension Problems, Embedding graphs in the torus in linear time, A matrix analysis of carrier posets of biconnected graphs, A large set of torus obstructions and how they were discovered, Orthogonal drawings of graphs for the automation of VLSI circuit design, Menus of kuratowski subgraphs, 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, A characterization of planar graphs by Trémaux orders