В теории графов внешнепланарный граф — это граф, имеющий планарный рисунок , все вершины которого принадлежат внешней грани рисунка.
Внепланарные графы могут быть охарактеризованы (аналогично теореме Вагнера для плоских графов) двумя запрещенными минорами K 4 и K 2,3 или их инвариантами графа Колена де Вердьера . Они имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует уникальный гамильтонов цикл. Каждый внешнепланарный граф раскрашивается в 3 цвета, имеет вырожденность и древовидную ширину не более 2.
Внешнепланарные графы — это подмножество плоских графов , подграфов последовательно-параллельных графов и круговых графов . Максимальные внешнепланарные графы , к которым нельзя добавить больше ребер при сохранении внешнепланарности, также являются хордальными графами и графами видимости .
Внешнепланарные графы были впервые изучены и названы Чартраном и Харари (1967) в связи с проблемой определения планарности графов, сформированных с помощью идеального паросочетания для соединения двух копий базового графа (например, многих обобщенных графов Петерсена). формируются таким образом из двух копий графа цикла ). Как они показали, когда базовый граф двусвязен , граф, построенный таким образом, является планарным тогда и только тогда, когда его базовый граф является внешнепланарным и сопоставление образует двугранную перестановку его внешнего цикла. Чартран и Харари также доказали аналог теоремы Куратовского для внешнепланарных графов, согласно которому граф является внешнепланарным тогда и только тогда, когда он не содержит подразделения одного из двух графов K 4 или K 2,3 .
Внешнепланарный граф — это неориентированный граф , который можно нарисовать на плоскости без пересечений так, чтобы все вершины принадлежали неограниченной грани рисунка. То есть ни одна вершина не окружена полностью ребрами. Альтернативно, граф G является внешнепланарным, если граф, образованный из G путем добавления новой вершины с ребрами, соединяющими его со всеми другими вершинами, является плоским графом . [1]
Максимальный внешнепланарный граф — это внешнепланарный граф, к которому не могут быть добавлены дополнительные ребра при сохранении внешнепланарности. Каждый максимальный внешнепланарный граф с n вершинами имеет ровно 2 n − 3 ребра, и каждая ограниченная грань максимального внешнепланарного графа является треугольником.
Внепланарные графы имеют запрещенную характеристику графа, аналогичную теореме Куратовского и теореме Вагнера для плоских графов: граф является внешнепланарным тогда и только тогда, когда он не содержит подразделения полного графа K 4 или полного двудольного графа K 2,3 . [2] Альтернативно, граф является внешнепланарным тогда и только тогда, когда он не содержит K 4 или K 2,3 в качестве минора , графа, полученного из него путем удаления и сжатия ребер. [3]
Граф без треугольников является внешнепланарным тогда и только тогда, когда он не содержит подразделения K 2,3 . [4]
Граф является внешнепланарным тогда и только тогда, когда его инвариант графа Колена де Вердьера не превосходит двух. Графы, характеризующиеся аналогичным образом тем, что инвариант Колена де Вердьера не превышает одного, трех или четырех, представляют собой соответственно линейные леса, плоские графы и встраиваемые без связей графы .
An outerplanar graph is biconnected if and only if the outer face of the graph forms a simple cycle without repeated vertices. An outerplanar graph is Hamiltonian if and only if it is biconnected; in this case, the outer face forms the unique Hamiltonian cycle.[5] 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.[6]
A planar graph is outerplanar if and only if each of its biconnected components is outerplanar.[4]
All loopless outerplanar graphs can be colored using only three colors;[7] this fact features prominently in the simplified proof of Chvátal's art gallery theorem by Fisk (1978). A 3-coloring may be found in linear time by a greedy coloring algorithm that removes any vertex of degree at most two, colors the remaining graph recursively, and then adds back the removed vertex with a color different from the colors of its two neighbors.
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.[8] 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.[7]
Внешнепланарные графы имеют вырождение не более двух: каждый подграф внешнепланарного графа содержит вершину степени не выше двух. [9]
Внепланарные графы имеют ширину дерева не более двух, что означает, что многие задачи оптимизации графов, которые являются NP-полными для произвольных графов, могут быть решены за полиномиальное время с помощью динамического программирования , когда входные данные являются внешнепланарными. В более общем смысле k -внепланарные графы имеют ширину дерева O( k ). [10]
Каждый внешнепланарный граф можно представить как граф пересечений прямоугольников на плоскости, выровненных по осям, поэтому внешнепланарные графы имеют квадратичность не более двух. [11]
Каждый внешнепланарный граф является планарным графом . Каждый внешнепланарный граф также является подграфом последовательно-параллельного графа . [12] Однако не все плоские последовательно-параллельные графы являются внешнепланарными. Полный двудольный граф K 2,3 является плоским и последовательно-параллельным, но не внешнепланарным. С другой стороны, полный граф K 4 планарен, но не является ни последовательно-параллельным, ни внешнепланарным. Каждый лес и каждый граф кактуса внешнепланарны. [13]
Слабый планарный двойственный граф вложенного внешнепланарного графа (граф, который имеет вершину для каждой ограниченной грани вложения и ребро для каждой пары соседних ограниченных граней) является лесом, а слабый планарный двойственный графу Халина — это внешнепланарный граф. Планарный граф является внешнепланарным тогда и только тогда, когда его слабый двойник является лесом, и он является халинским тогда и только тогда, когда его слабый двойник двусвязен и внешнепланарен. [14]
Существует понятие степени внешнепланарности. 1-внепланарное вложение графа аналогично внешнепланарному вложению. При k > 1 плоское вложение называется k -внепланарным, если удаление вершин на внешней грани приводит к ( k − 1)-внепланарному вложению. Граф называется k -внепланарным, если он имеет k -внепланарное вложение. [15]
Внешний 1-планарный граф , аналогично 1-планарным графам , можно нарисовать в диске с вершинами на границе диска и не более чем с одним пересечением на каждом ребре.
Каждый максимальный внешнепланарный граф является хордальным графом . Каждый максимальный внешнепланарный граф является графом видимости простого многоугольника . [16] Максимальные внешнепланарные графы также формируются как графы триангуляций многоугольников . Они являются примерами 2-деревьев , последовательно-параллельных графов и хордальных графов .
Каждый внешнепланарный граф представляет собой круговой граф , граф пересечений набора хорд окружности. [17]