de Fraysseix, Hubert; Ossona de Mendez, Patrice On cotree-critical and DFS cotree-critical graphs. (English) Zbl 1061.05081 J. Graph Algorithms Appl. 7, No. 4, 411-427 (2003). 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. Cited in 6 Documents MSC: 05C75 Structural characterization of families of graphs Keywords:cotree-critical graphs; algorithm Software:PIGALE PDFBibTeX XMLCite \textit{H. de Fraysseix} and \textit{P. Ossona de Mendez}, J. Graph Algorithms Appl. 7, No. 4, 411--427 (2003; Zbl 1061.05081) Full Text: DOI EuDML