Connectivity of Planar Graphs
Hubert de Fraysseix, Patrice Ossona de Mendez · 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.