A Characterization of DFS Cotree Critical Graphs

De Fraysseix, Hubert and Ossona de Mendez, Patrice (2002) A Characterization of DFS Cotree Critical Graphs. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 84-95 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_7).

Full text not available from this repository.

Abstract

We give a characterization of DFS-cotree critical graphs which is central to the linear time Kuratowski finding algorithm implemented in PIGALE.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_7
Classifications:Z Theory > Z.001 General
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:403

Repository Staff Only: item control page

References

H. de Fraysseix and P. Ossona de Mendez, An algorithm to find Kuratowski subdivision in DFS cotree critical graphs, Proceedings of the twelfth australasian workshop on combinatorial algorithms (Edy Try Baskoro, ed.), Institut Teknologi Bandung, Indonesia, 2001.

H. de Fraysseix and P. Rosenstiehl, A discriminatory theorem of Kuratowski subgraphs, Lecture Notes in Mathematics 1018 (1981), 214-222.

_______, A chracterization of planar graphs by Trémaux orders, Combinatorica 5 (1985), no. 2, 127-135.

J.E. Hopcroft and R.E. Tarjan, Efficient planarity testing, J. Assoc. Comput. Math. 21 (1974), 549-568.

K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. 15 (1930), 271-293.

W.T. Tutte, Graph theory, Encyclopedia of Mathematics and its applications, vol. 21, Addison-Wesley, 1984.

S.G. Williamson, Depth-first search and kuratowski subgraphs, Journal of the ACM 31 (1984), no. 4, 681-693.