Внепланарный граф

Максимальный внешнепланарный граф и его 3-раскраска

Полный граф K ₄ — это наименьший планарный граф, не являющийся внешнепланарным.

В теории графов внешнепланарный граф — это граф, имеющий планарный рисунок , все вершины которого принадлежат внешней грани рисунка.

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

Внешнепланарные графы — это подмножество плоских графов , подграфов последовательно-параллельных графов и круговых графов . Максимальные внешнепланарные графы , к которым нельзя добавить больше ребер при сохранении внешнепланарности, также являются хордальными графами и графами видимости .

История

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

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

Внешнепланарный граф — это неориентированный граф , который можно нарисовать на плоскости без пересечений так, чтобы все вершины принадлежали неограниченной грани рисунка. То есть ни одна вершина не окружена полностью ребрами. Альтернативно, граф G является внешнепланарным, если граф, образованный из G путем добавления новой вершины с ребрами, соединяющими его со всеми другими вершинами, является плоским графом .

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

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

Внепланарные графы имеют характеристику запрещенного графа, аналогичную теореме Куратовского и теореме Вагнера для плоских графов: граф является внешнепланарным тогда и только тогда, когда он не содержит подразделения полного графа K ₄ или полного двудольного графа K _2,3 . Альтернативно, граф является внешнепланарным тогда и только тогда, когда он не содержит K ₄ или K _2,3 в качестве минора , графа, полученного из него удалением и сжатием ребер.

Граф без треугольников является внешнепланарным тогда и только тогда, когда он не содержит подразделения K _2,3 .

Колен Инвариант Вердьера

Граф является внешнепланарным тогда и только тогда, когда его инвариант графа Колена де Вердьера не превосходит двух. Графы, характеризующиеся аналогичным образом наличием инварианта Колена де Вердьера не более одного, трех или четырех, представляют собой соответственно линейные леса, плоские графы и бессвязно встраиваемые графы .

Характеристики

Двусвязность и гамильтоновость

Внешнепланарный граф является двусвязным тогда и только тогда, когда внешняя грань графа образует простой цикл без повторяющихся вершин. Внешнепланарный граф является гамильтоновым тогда и только тогда, когда он двусвязен; в этом случае внешняя грань образует единственный гамильтонов цикл. В более общем смысле, размер самого длинного цикла во внешнепланарном графе равен количеству вершин в его наибольшем двусвязном компоненте . По этой причине нахождение гамильтоновых циклов и самых длинных циклов во внешнепланарных графах может быть решено за линейное время , в отличие от NP-полноты этих задач для произвольных графов.

Каждый максимальный внешнепланарный граф удовлетворяет более сильному условию, чем гамильтоновость: он является панциклическим по узлам , что означает, что для каждой вершины v и каждого k в диапазоне от трех до числа вершин в графе существует цикл длины k , содержащий v . Цикл такой длины можно найти, многократно удаляя треугольник, который соединен с остальной частью графа одним ребром, так что удаленная вершина не равна v , пока внешняя грань оставшегося графа не достигнет длины k .

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

Раскраска

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

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

Другие объекты недвижимости

Внешнепланарные графы имеют вырождение не более двух: каждый подграф внешнепланарного графа содержит вершину степени не выше двух.

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

Каждый внешнепланарный граф можно представить как граф пересечений прямоугольников на плоскости, выровненных по осям, поэтому внешнепланарные графы имеют квадратичность не более двух.

Родственные семейства графов

График кактуса . Кактусы образуют подкласс внешнепланарных графов.

Каждый внешнепланарный граф является планарным графом . Каждый внешнепланарный граф также является подграфом последовательно-параллельного графа . Однако не все плоские последовательно-параллельные графы являются внешнепланарными. Полный двудольный граф K _2,3 является плоским и последовательно-параллельным, но не внешнепланарным. С другой стороны, полный граф K ₄ планарен, но не является ни последовательно-параллельным, ни внешнепланарным. Каждый лес и каждый граф кактуса внешнепланарны.

Слабый планарный двойственный граф вложенного внешнепланарного графа (граф, который имеет вершину для каждой ограниченной грани вложения и ребро для каждой пары соседних ограниченных граней) является лесом, а слабый планарный двойственный графу Халина — это внешнепланарный граф. Планарный граф является внешнепланарным тогда и только тогда, когда его слабый двойник является лесом, и он является халинским тогда и только тогда, когда его слабый двойник двусвязен и внешнепланарен.

Существует понятие степени внешнепланарности. 1-внепланарное вложение графа аналогично внешнепланарному вложению. При k > 1 плоское вложение называется k -внепланарным, если удаление вершин на внешней грани приводит к ( k − 1)-внепланарному вложению. Граф называется k -внепланарным, если он имеет k -внепланарное вложение.

Внешний 1-планарный граф , аналогично 1-планарным графам, можно нарисовать в диске с вершинами на границе диска и не более чем с одним пересечением на каждом ребре.

Каждый максимальный внешнепланарный граф является хордальным графом . Каждый максимальный внешнепланарный граф является графом видимости простого многоугольника . Максимальные внешнепланарные графы формируются также как графы триангуляций многоугольников . Они являются примерами 2-деревьев , последовательно-параллельных графов и хордальных графов .

Каждый внешнепланарный граф представляет собой круговой граф , граф пересечений набора хорд окружности.

Ссылки

• Бейкер, Бренда С. (1994), «Алгоритмы аппроксимации для NP-полных задач на плоских графах», Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID   9706753 .
• Боза, Луис; Федриани, Эухенио М.; Нуньес, Хуан (2004), «Проблема внешних вложений в псевдоповерхности», Ars Combinatoria , 71 : 79–91 .
• Боза, Луис; Федриани, Эухенио М.; Нуньес, Хуан (2004), «Наборы препятствий для графов внешней банановой поверхности», Ars Combinatoria , 73 : 65–77 .
• Боза, Луис; Федриани, Эухенио М.; Нуньес, Хуан (2006), «Несчетные графы со всеми вершинами на одной грани», Acta Mathematica Hungarica , 112 (4): 307–313, doi : 10.1007/s10474-006-0082-0 , S2CID   123241658 .
• Боза, Луис; Федриани, Эухенио М.; Нуньес, Хуан (2010), «Внешняя вложимость в некоторые псевдоповерхности, возникающие из трех сфер», Discrete Mathematics , 310 (23): 3359–3367, doi : 10.1016/j.disc.2010.07.027 .
• Брандштедт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, Общество промышленной и прикладной математики , ISBN  0-89871-432-Х .
• Шартран, Гэри ; Харари, Франк (1967), «Плоские графы перестановок» , Annales de l'Institut Henri Poincaré B , 3 (4): 433–438, MR   0227041 .
• Дистель, Рейнхард (2000), Теория графов , Тексты для аспирантов по математике , том. 173, Шпрингер-Верлаг, с. 107, ISBN  0-387-98976-5 .
• Эль-Гинди, Х. (1985), Иерархическая декомпозиция полигонов с приложениями , доктор философии. диссертация, Университет Макгилла . Цитируется Брандштедтом, Ле и Спинрадом (1999) .
• Фельснер, Стефан (2004), Геометрические графы и схемы: некоторые главы из комбинационной геометрии , Vieweg+Teubner Verlag, стр. 6, ISBN  978-3-528-06972-8 .
• Фиорини, Стэнли (1975), «О хроматическом индексе внешнепланарных графов», Журнал комбинаторной теории , серия B, 18 (1): 35–38, doi : 10.1016/0095-8956(75)90060-X .
• Фиск, Стив (1978), «Краткое доказательство теоремы Хваталя о стороже», Журнал комбинаторной теории , серия B, 24 (3): 374, номер документа : 10.1016/0095-8956(78)90059-X .
• Флейшнер, Герберт Дж.; Геллер, ДП; Харари, Франк (1974), «Внепланарные графы и слабые двойственные графы», Журнал Индийского математического общества , 38 : 215–219, MR   0389672 .
• Кейн, Винай Г.; Басу, Санат К. (1976), «О глубине плоского графа», Discrete Mathematics , 14 (1): 63–67, doi : 10.1016/0012-365X(76)90006-6 .
• Ли, Мин-Чу; Корнейл, Дерек Г .; Мендельсон, Эрик (2000), «Панцикличность и NP-полнота в плоских графах», Discrete Applied Mathematics , 98 (3): 219–225, doi : 10.1016/S0166-218X(99)00163-8 .
• Лик, Дон Р.; Уайт, Артур Т. (1970), « k -вырожденные графы» , Canadian Journal of Mathematics , 22 (5): 1082–1096, doi : 10.4153/CJM-1970-125-1 , S2CID   124609794 .
• Лин, Яу-Линг; Скиена, Стивен С. (1995), «Аспекты сложности графов видимости», Международный журнал вычислительной геометрии и приложений , 5 (3): 289–312, doi : 10.1142/S0218195995000179 .
• Проскуровский, Анджей; Сысло, Мачей М. (1986), «Эффективная раскраска вершин и ребер внешнепланарных графов», SIAM Journal on Algebraic and Discrete Methods , 7 : 131–136, doi : 10.1137/0607016 .
• Шайнерман, Э.Р. (1984), Классы пересечений и множественные параметры пересечения графа , доктор философии. диссертация, Принстонский университет . Цитируется Брандштедтом, Ле и Спинрадом (1999) .
• Сысло, Мацей М. (1979), «Характеристики внешнепланарных графов», Discrete Mathematics , 26 (1): 47–53, doi : 10.1016/0012-365X(79)90060-8 .
• Сысло, Мацей М.; Проскуровский, Анджей (1983), «О графах Халина», Теория графов: материалы конференции, состоявшейся в Лагуве, Польша, 10–13 февраля 1981 г. , Конспекты лекций по математике , том. 1018, Springer-Verlag, стр. 248–256, doi : 10.1007/BFb0071635 .
• Унгер, Уолтер (1988), «О k -раскраске круговых графов», Proc. 5-й симпозиум по теоретическим аспектам информатики (STACS '88) , Конспекты лекций по информатике , том. 294, Springer-Verlag, стр. 61–72, doi : 10.1007/BFb0035832 .
• Вессель, В.; Пёшель, Р. (1985), «О круговых графах», в Саксе, Хорсте (ред.), Графы, гиперграфы и приложения: материалы конференции по теории графов, проходившей в Эйбе, с 1 по 5 октября 1984 г. , Teubner-Texte zur Mathematik, vol. 73, Б. Г. Тойбнер, стр. 207–210 . Цитируется Унгером (1988) .
• Вигерс, Манфред (1986), «Распознавание внешнепланарных графов в линейном времени», Конспект лекций по информатике , 246 : 165–176, doi : 10.1007/3-540-17218-1_57 .

Внешние ссылки

• Внепланарные графы в Информационной системе классов графов и их включений
• Вайсштейн, Эрик В. «Внепланарный граф» . Математический мир .