Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00077 On Cotree-Critical and DFS Cotree-Critical Graphs Hubert de Fraysseix and Patrice Ossona de Mendez Vol. 7, no. 4, pp. 411-427, 2003. Regular paper Abstract We give a characterization of DFS cotree-critical graphs which is central to the linear time Kuratowski finding 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.
|
Revised: August 2003. Submitted: May 2002. Communicated by Petra Mutzel and Michael Jünger |
| Journal of Graph Algorithms and Applications |