Outerplanar

Outerplanar graphs are graphs that can be drawn in the plane without edge crossings in such a way that all vertices lie on the boundary of the outer (unbounded) face. In other words, there exists a plane embedding where every vertex is incident to the outer face. Every outerplanar graph is planar, but not every planar graph is outerplanar.

A standard characterization is by forbidden minors: a graph is outerplanar if and only if it contains no K4 or K2,3 as a minor. Equivalently, it can be drawn so that all vertices lie on a common circle with non-crossing interior edges, although the planar embedding with all vertices on the outer face suffices for the definition.

Maximal outerplanar graphs are outerplanar graphs to which no additional edge can be added without destroying outerplanarity. They correspond to triangulations of a polygon: with n vertices they have exactly 2n−3 edges, and every interior face is a triangle. They are 2-connected and chordal, and every pair of consecutive vertices on the outer boundary forms a triangle with a third vertex.

Outerplanar graphs have several structural properties. They have degeneracy at most 2, meaning every subgraph contains a vertex of degree at most 2. Consequently, they have treewidth at most 2 and admit linear-time algorithms for many computational problems. Recognizing outerplanarity can likewise be performed in linear time.

Examples include cycles Cn and the triangle K3; graphs like K4 and K2,3 are not outerplanar. Outerplanar graphs form a proper subclass of planar graphs and relate to broader graph families such as series-parallel graphs, offering favorable algorithmic characteristics.