Depth-First Search and Kuratowski Subgraphs

DOI10.1145/1634.322451zbMath0632.68063OpenAlexW2161714963WikidataQ56092455 ScholiaQ56092455MaRDI QIDQ3769978

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

linear time algorithmsnonplanar graphKuratowski subgraphefficient graph algorithms

Mathematics Subject Classification ID

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

Related Items (15)

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Outer 1-planar graphs ⋮ Unnamed Item ⋮ Searching forK_3,3in linear time ⋮ On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm ⋮ 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 ⋮ Canonical forms for cycles in bridge graphs ⋮ Linkless and flat embeddings in 3-space ⋮ A large set of torus obstructions and how they were discovered ⋮ A new planarity test ⋮ Certifying algorithms ⋮ Menus of kuratowski subgraphs ⋮ Efficient Extraction of Multiple Kuratowski Subdivisions

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