Outerplanar graph

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

G is k-outerplanar if for k = 1 G is an outerplanar graph and for k > 1 G has a planar embedding such that if all vertices on the exterior face are deleted, the connected components of the remaining graph are all (k-1)-outerplanar. See also Halin graph.