Depth-First Search and Kuratowski Subgraphs

DOI10.1145/1634.322451MaRDI QIDQ3769978zbMATH OpenOpenAlexWikidataFDO

Authors S. Gill Williamson

Publication date 1984

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1634.322451

zbMATH Keywords

efficient graph algorithmsKuratowski subgraphlinear time algorithmsnonplanar graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(20)

• Projective plan and Möbius band obstructions
• Relational depth-first-search with applications
• A large set of torus obstructions and how they were discovered
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm
• A new planarity test
• Elimination of local bridges
• Outer 1-planar graphs
• Menus of kuratowski subgraphs
• Searching forK_3,3in linear time
• Linkless and flat embeddings in 3-space
• Obstructions for the Disk and the Cylinder Embedding Extension Problems
• Canonical forms for cycles in bridge graphs
• scientific article; zbMATH DE number 1069483 (Why is no real title available?)
• Certifying algorithms
• On the existence of special depth first search trees
• Embedding graphs in the torus in linear time
• Efficient Extraction of Multiple Kuratowski Subdivisions
• Depth-First Search in Directed Planar Graphs, Revisited
• Efficient polynomial-time approximation scheme for the genus of dense graphs

This page was built for publication: Depth-First Search and Kuratowski Subgraphs

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