Depth-First Search and Kuratowski Subgraphs

1984/09/20 by S. Gill Williamson · 63 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #semigroups and automata theory #Citation #Computer science #Information retrieval #World Wide Web #Library science

paper · pdf · doi:10.1145/1634.322451

published in Journal of the ACM 31(4), 681-693 (Association for Computing Machinery)

openalex publication_date 1984/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

Lel G = (V, E) be a nonplanar graph. The method of using depth-first techniques to extract a Kuratowski .

Citations

• Efficient Planarity Testing
• Depth-First Search and Linear Graph Algorithms

Cited by

• The Bidimensionality Theory and Its Algorithmic Applications
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Planarity Allowing Few Error Vertices in Linear Time
• Planarity testing [wikipedia]