×

On cotree-critical and DFS cotree-critical graphs. (English) Zbl 1061.05081

Summary: We give a characterization of DFS cotree-critical graphs which is central to finding the linear time Kuratowski algorithm implemented in PIGALE (Public Implementation of a Graph Algorithm Library and Editor) by the authors, and deduce a justification of a very simple algorithm for finding a Kuratowski subdivision in a DFS cotree-critical graph.

MSC:

05C75 Structural characterization of families of graphs

Software:

PIGALE
PDFBibTeX XMLCite
Full Text: DOI EuDML