Page "Outerplanar graph" Paragraph 5

An outerplanar graph is biconnected if and only if the outer face of the graph forms a simple cycle without repeated vertices.

An outerplanar graph is Hamiltonian if and only if it is biconnected ; in this case, the outer face forms the unique Hamiltonian cycle.

More generally, the size of the longest cycle in an outerplanar graph is the same as the number of vertices in its largest biconnected component.

For this reason finding Hamiltonian cycles and longest cycles in outerplanar graphs may be solved in linear time, in contrast to the NP-completeness of these problems for arbitrary graphs.