A Depth-First-Search Characterization of Planarity

DOI10.1016/S0304-0208(08)73550-3MaRDI QIDQ3960721zbMATH OpenOpenAlexFDO

Authors Hubert de Fraysseix, Pierre Rosenstiehl

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

cocycledepth-first searchgraph embeddingplanaritytremaux tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(16)

• 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
• Elimination of local bridges
• 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.

This page was built for publication: A Depth-First-Search Characterization of Planarity

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