de Fraysseix, H.; Ossona de Mendez, P.

Connectivity of planar graphs

J. Graph Algorithms Appl. 5(5), 93-105 (2001)


Summary: We give here three simple linear time algorithms on planar graphs: a 4-connexity test for maximal planar graphs, an algorithm enumerating the triangles and a 3-connexity test. Although all these problems got already linear-time solutions, the presented algorithms are both simple and efficient. They are based on some new theoretical results. Communicated by T. Nishizeki, R. Tamassia and D. Wagner: