Outerplanar graph

Материал из WikiGrapp
Версия от 16:34, 7 июня 2011; Glk (обсуждение | вклад) (Новая страница: «'''Outerplanar graph''' --- внешнепланарный граф. A graph <math>G</math> is ''' outerplanar''' if there is a crossing-free embedding of <math>G<…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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.