×

zbMATH — the first resource for mathematics

Depth-first search and Kuratowski subgraphs. (English) Zbl 0632.68063
Let \(G=(V,E)\) be a nonplanar graph. The method of using depth-first techniques to extract a Kuratowski subgraph in time O(\(| V|)\) is shown.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX XML Cite
Full Text: DOI