Введение

Непересекающийся граф с вершинами на внешней грани

В теории графов, внешнепланарный граф — это граф, имеющий планарное изображение, в котором все вершины лежат на внешней грани изображения. Внешнепланарные графы могут быть охарактеризованы (аналогично теореме Вагнера для планарных графов) двумя запрещенными минорами K4 и K2,3, или их инвариантами графа Колина де Вердьера. Они содержат гамильтонов цикл тогда и только тогда, когда они бисвязны, в этом случае внешняя грань образует единственный гамильтонов цикл. Каждый внешнепланарный граф 3-окрасим, и имеет вырождение и древесную ширину не более 2. Внешнепланарные графы являются подмножеством планарных графов, подграфов серийно-параллельных графов и круговых графов. Максимальные внешнепланарные графы, к которым нельзя добавить больше ребер, сохраняя внешнепланарность, также являются хордальными графами и графами видимости.

История

Внешнепланарные графы были впервые изучены и названы в связи с задачей определения планарности графов, образованных использованием совершенного паросочетания для соединения двух копий базового графа (например, многие обобщенные графы Петерсена формируются таким образом из двух копий циклического графа). Как они показали, когда базовый граф двусвязный, граф, построенный таким образом, является планарным тогда и только тогда, когда его базовый граф внешнепланарен, а паросочетание образует диэдрическую перестановку его внешней границы. Шартран и Харари также доказали аналогичную теореме Куратовского теорему для внешнепланарных графов, утверждающую, что граф является внешнепланарным тогда и только тогда, когда он не содержит подграф, являющийся делением одного из двух графов K4 или K2,3.

Определение и характеристики

Внешнепланарный граф — это неориентированный граф, который можно нарисовать на плоскости без пересечений так, чтобы все вершины лежали на неограниченной области рисунка. Иными словами, ни одна вершина не окружена полностью рёбрами. Альтернативно, граф G является внешнепланарным, если граф, полученный из G добавлением новой вершины и соединением её рёбрами со всеми остальными вершинами, является планарным графом. Максимальный внешнепланарный граф — это внешнепланарный граф, к которому нельзя добавить ни одного ребра, сохраняя при этом внешнепланарность. Каждый максимальный внешнепланарный граф с n вершинами имеет ровно 2n − 3 рёбер, и каждая ограниченная область максимального внешнепланарного графа является треугольником.

Запрещенные графики

Внешнепланарные графы имеют запрещенную характеристику графа, аналогичную теореме Куратовского и теореме Вагнера для планарных графов: граф является внешнепланарным тогда и только тогда, когда он не содержит подграф, являющийся подразделением полного графа K4 или полного двудольного графа K2,3. Альтернативно, граф является внешнепланарным тогда и только тогда, когда он не содержит K4 или K2,3 в качестве минора – графа, полученного из него путем удаления и сжатия ребер. Треугольник-свободный граф является внешнепланарным тогда и только тогда, когда он не содержит подразделение K2,3. В более общем случае, длина самого длинного цикла во внешнепланарном графе равна числу вершин в его наибольшей двусвязной компоненте. По этой причине поиск гамильтоновых циклов и самых длинных циклов во внешнепланарных графах может быть решен за линейное время, в отличие от NP-полноты этих задач для произвольных графов. Каждый максимальный внешнепланарный граф удовлетворяет более сильному условию, чем гамильтоновость: он является узел-панциклическим, что означает, что для каждой вершины v и каждого k в диапазоне от трех до числа вершин в графе существует цикл длины k, содержащий v. Цикл такой длины можно найти, последовательно удаляя треугольник, который соединен с остальной частью графа единственным ребром, при этом удаляемая вершина не является v, пока длина внешней грани оставшегося графа не станет равной k.

Планарный граф является внешнепланарным тогда и только тогда, когда каждая из его двусвязных компонент является внешнепланарной.

Цветение

Все петлелишенные внешнепланарные графы могут быть раскрашены с использованием только трех цветов; этот факт играет важную роль в упрощенном доказательстве теоремы о художественной галерее Чваттала. Раскраска в три цвета может быть найдена за линейное время с помощью жадного алгоритма раскраски, который удаляет любую вершину степени не более двух, рекурсивно раскрашивает оставшийся граф, а затем добавляет удаленную вершину, используя цвет, отличный от цветов ее двух соседей. Согласно теореме Визинга, хроматический индекс любого графа (минимальное количество цветов, необходимое для раскраски его ребер так, чтобы никакие два смежных ребра не имели один и тот же цвет) равен либо максимальной степени любой вершины графа, либо максимальной степени плюс один. Однако в связном внешнепланарном графе хроматический индекс равен максимальной степени, за исключением случая, когда граф образует цикл нечетной длины. Раскраска ребер с оптимальным количеством цветов может быть найдена за линейное время на основе обхода в ширину слабого двойственного дерева. Внешнепланарные графы имеют ширину дерева не более двух, что означает, что многие задачи оптимизации графов, являющиеся NP-полными для произвольных графов, могут быть решены за полиномиальное время с помощью динамического программирования, если входные данные являются внешнепланарными. В более общем случае, k-внешнепланарные графы имеют ширину дерева O(k). Любой внешнепланарный граф может быть представлен как граф пересечений осевых прямоугольников на плоскости, следовательно, внешнепланарные графы имеют боксичность не более двух.

Связанные семейства графиков

Каждый внешнепланарный граф является плоским графом. Каждый внешнепланарный граф также является подграфом графа, являющегося серией-параллельным. Однако не все плоские графы, являющиеся серией-параллельными, являются внешнепланарными. Полный двудольный граф K2,3 является плоским и серией-параллельным, но не внешнепланарным. С другой стороны, полный граф K4 является плоским, но не является ни серией-параллельным, ни внешнепланарным. Каждый лес и каждый кактусный граф являются внешнепланарными. Слабый плоский двойственный граф вложенного внешнепланарного графа (граф, имеющий вершину для каждой ограниченной грани вложения и ребро для каждой пары смежных ограниченных граней) является лесом, а слабый плоский двойственный граф графа Халина является внешнепланарным графом. Плоский граф является внешнепланарным тогда и только тогда, когда его слабый двойственный граф является лесом, и он является графом Халина тогда и только тогда, когда его слабый двойственный граф является бисвязным и внешнепланарным. Существует понятие степени внешнепланарности. 1-внешнепланарное вложение графа то же самое, что и внешнепланарное вложение. Для k > 1 плоское вложение называется k-внешнепланарным, если удаление вершин на внешней грани приводит к (k - 1)-внешнепланарному вложению. Граф является k-внешнепланарным, если он имеет k-внешнепланарное вложение. Внешний 1-планарный граф, аналогично 1-планарным графам, может быть изображен на диске, с вершинами на границе диска и не более чем с одним пересечением на ребро. Каждый максимальный внешнепланарный граф является хордальным графом. Каждый максимальный внешнепланарный граф является графом видимости простого многоугольника. Максимальные внешнепланарные графы также формируются как графы триангуляций многоугольников. Они являются примерами 2-деревьев, графов, являющихся серией-параллельными, и хордальных графов. Каждый внешнепланарный граф является круговым графом, графом пересечений набора хорд круга.