Outerplanar graph

Every maximal outerplanar graph with n vertices has exactly 2n − 3 edges, and every bounded face of a maximal outerplanar graph is a triangle.

[6] 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.

Every maximal outerplanar graph satisfies a stronger condition than Hamiltonicity: it is node pancyclic, meaning that for every vertex v and every k in the range from three to the number of vertices in the graph, there is a length-k cycle containing v. A cycle of this length may be found by repeatedly removing a triangle that is connected to the rest of the graph by a single edge, such that the removed vertex is not v, until the outer face of the remaining graph has length k.[7] A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.

[5] All loopless outerplanar graphs can be colored using only three colors;[8] this fact features prominently in the simplified proof of Chvátal's art gallery theorem by Fisk (1978).

According to Vizing's theorem, the chromatic index of any graph (the minimum number of colors needed to color its edges so that no two adjacent edges have the same color) is either the maximum degree of any vertex of the graph or one plus the maximum degree.

However, in a connected outerplanar graph, the chromatic index is equal to the maximum degree except when the graph forms a cycle of odd length.

[9] An edge coloring with an optimal number of colors can be found in linear time based on a breadth-first traversal of the weak dual tree.

The complete bipartite graph K2,3 is planar and series–parallel but not outerplanar.

On the other hand, the complete graph K4 is planar but neither series–parallel nor outerplanar.