Outerplanar graph

Outerplanar graph --- внешнепланарный граф.

A graph [math]\displaystyle{ G }[/math] is outerplanar if there is a crossing-free embedding of [math]\displaystyle{ G }[/math] in the plane such that all vertices are on the same face. [math]\displaystyle{ G }[/math] is outerplanar iff [math]\displaystyle{ G }[/math] contains no subgraph homeomorphic to [math]\displaystyle{ K_{4} }[/math] or [math]\displaystyle{ K_{2,3} }[/math] by a homeomorphism that deletes degree-2 vertices but does not add them.

[math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-outerplanar if for [math]\displaystyle{ k = 1 }[/math] [math]\displaystyle{ G }[/math] is an outerplanar graph and for [math]\displaystyle{ k \gt 1 }[/math] [math]\displaystyle{ G }[/math] has a planar embedding such that if all vertices on the exterior face are deleted, the connected components of the remaining graph are all [math]\displaystyle{ (k-1) }[/math]-outerplanar. See also Halin graph.