Connectivity of Planar Graphs - de Fraysseix, Hubert; Ossona de Mendez, Patrice (Journal of Graph Algorithms and Applications, 2001)
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.