Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
Connectivity of Planar Graphs
Vol. 5, no. 5, pp. 93-105, 2001. Regular paper.
Abstract 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.
Submitted: February 1999.
Revised: April 2000.
article (PDF)