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 enumeratingthe triangles and a 3-connexity test. Although all these problems gotalready linear-time solutions, the presented algorithms are both simpleand efficient. They are based on some new theoretical results.