A Depth-First-Search Characterization of Planarity

DOI10.1016/S0304-0208(08)73550-3zbMath0497.05026MaRDI QIDQ3960721

Pierre Rosenstiehl, Hubert de Fraysseix

Publication date: 1982

Published in: Graph Theory, Proceedings of the Conference on Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-0208(08)73550-3

zbMATH Keywords

planarity; cocycle; depth-first search; graph embedding; tremaux tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

Related Items

Triangulating planar graphs while minimizing the maximum degree, Recent Advances in Exact Crossing Minimization (Extended Abstract), Trémaux Trees and Planarity, Planarity for clustered graphs, Trémaux trees and planarity, Bipartite graphs, upward drawings, and planarity, Upward drawings of triconnected digraphs., Representations of graphs and networks (coding, layouts and embeddings), Area requirement and symmetry display of planar upward drawings, A large set of torus obstructions and how they were discovered, Facilities layout generalized model solved by n-boundary shortest path heuristics, Upward planarity testing, On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm, Orthogonal drawings of graphs for the automation of VLSI circuit design, On Boolean characterizations of planarity and planar embeddings of graphs, Unnamed Item