1-планарный граф
В топологической теории графов — 1-планарный граф это граф, который можно нарисовать на евклидовой плоскости таким образом, что каждое ребро имеет не более одной точки пересечения, где оно пересекает одно дополнительное ребро. Если 1-плоскостной граф, одно из наиболее естественных обобщений плоских графов , нарисован таким образом, то рисунок называется 1-плоскостным графом или 1-планарным вложением графа .
Раскраска
[ редактировать ]1-планарные графы были впервые изучены Рингелем (1965) , который показал, что их можно раскрасить не более чем в семь цветов. [1] Позже было показано, что точное количество цветов, необходимых для раскраски этих графов, в худшем случае равно шести. [2] Пример полного графа K 6 , который является 1-планарным, показывает, что 1-планарные графы иногда могут требовать шести цветов. Однако доказательство того, что шести цветов всегда достаточно, сложнее.
Мотивацией Рингеля была попытка решить вариант полной раскраски планарных графов , при котором одновременно раскрашиваются вершины и грани планарного графа таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет, никакие две соседние грани не имели одинакового цвета. цвет, и ни одна вершина и грань, прилегающие друг к другу, не имеют одинакового цвета. Очевидно, это можно сделать, используя восемь цветов, применив теорему о четырех цветах к данному графу и его двойственному графу отдельно, используя два непересекающихся набора по четыре цвета. Однако меньше цветов можно получить, сформировав вспомогательный граф, который имеет вершину для каждой вершины или грани данного планарного графа и в котором две вершины вспомогательного графа являются смежными всякий раз, когда они соответствуют смежным функциям данного планарного графа. Раскраска вершин вспомогательного графа соответствует раскраске вершин граней исходного планарного графа. Этот вспомогательный граф является 1-планарным, из чего следует, что задача Рингеля о раскраске вершин и граней также может быть решена с использованием шести цветов. [2] Граф К6 ; не может быть таким образом сформирован как вспомогательный граф, но тем не менее задача раскраски вершин-граней тоже иногда требует шести цветов например, если раскрашиваемый планарный граф представляет собой треугольную призму , то для его одиннадцати вершин и граней требуется шесть цветов, поскольку никаким трем из них нельзя дать один цвет. [3]
Плотность краев
[ редактировать ]Любой 1-планарный граф с n вершинами имеет не более 4 n − 8 ребер. [4] Более строго: каждый 1-плоскостной рисунок имеет не более n − 2 пересечений ; удаление одного ребра из каждой пересекающейся пары ребер приводит к образованию плоского графа, который может иметь не более 3 n - 6 ребер, из чего сразу следует 4 n - 8, ограничивающее количество ребер в исходном 1-планарном графе. [5] Однако в отличие от планарных графов (у которых все максимальные планарные графы на заданном множестве вершин имеют одинаковое количество ребер), существуют максимальные 1-планарные графы (графы, к которым нельзя добавить никакие дополнительные ребра при сохранении 1-планарности). ), которые имеют значительно меньше 4 n − 8 ребер. [6] Оценку максимально возможного числа ребер в 1-планарном графе в 4 n − 8 можно использовать, чтобы показать, что полный граф K 7 с семью вершинами не является 1-планарным, поскольку этот граф имеет 21 ребро и в этом случае 4 n − 8 = 20 < 21. [7]
1-планарный граф называется оптимальным 1-планарным графом , если он имеет ровно 4 n - 8 ребер, максимально возможное. В 1-планарном вложении оптимального 1-планарного графа непересекающиеся ребра обязательно образуют четырехугольник ( многогранный граф , в котором каждая грань является четырехугольником ). Таким образом, из каждого четырехугольника получается оптимальный 1-планарный граф путем добавления двух диагоналей к каждой из его четырехугольных граней. Отсюда следует, что каждый оптимальный 1-планарный граф является эйлеровым (все его вершины имеют четную степень ), что минимальная степень в таком графе равна шести и что каждый оптимальный 1-планарный граф имеет по крайней мере восемь вершин степени ровно шесть. Кроме того, каждый оптимальный 1-планарный граф является 4-связным , и каждый разрез с 4 вершинами в таком графе является разделяющим циклом в базовом четырехугольнике. [8]
Графы, которые имеют прямые 1-планарные рисунки (то есть рисунки, в которых каждое ребро представлено отрезком линии и в которых каждый отрезок пересекается не более чем одним другим ребром), имеют немного более жесткую границу 4 n - 9. на максимальном количестве ребер, достигаемом бесконечным количеством графов. [9]
Полные многодольные графы
[ редактировать ]
полная классификация 1-планарных полных графов , полных двудольных графов и, в более общем смысле, полных многодольных графов Известна . Всякий полный двудольный граф вида K 2, n является 1-планарным (даже планарным), как и всякий полный трехдольный граф вида K 1,1, n . Помимо этих бесконечных наборов примеров, единственными полными многодольными 1-планарными графами являются K 6 , K 1,1,1,6 , K 1,1,2,3 , K 2,2,2,2 , K 1, 1,1,2,2 и их подграфы. Минимальными не-1-планарными полными многодольными графами являются K 3,7 , K 4,5 , K 1,3,4 , K 2,3,3 и K 1,1,1,1,3 .Например, полный двудольный граф K 3,6 является 1-планарным, поскольку он является подграфом K 1,1,1,6 , но K 3,7 не является 1-планарным. [7]
Вычислительная сложность
[ редактировать ]NP -полна проверка того, является ли данный граф 1-планарным. [10] [11] и он остается NP-полным даже для графов, образованных из планарных графов добавлением единственного ребра [12] и для графиков ограниченной полосы пропускания . [13] Проблема решается с фиксированными параметрами, если она параметризована цикломатическим числом или глубиной дерева , поэтому ее можно решить за полиномиальное время , когда эти параметры ограничены. [13]
В отличие от теоремы Фари для плоских графов, не каждый 1-планарный граф можно нарисовать 1-планарно с отрезками прямых на его ребрах. [14] [15] Однако проверка возможности выпрямления одноплоскостного рисунка таким способом может быть выполнена за полиномиальное время . [16] Кроме того, каждый 1-планарный граф с 3 связями имеет 1-планарный рисунок, в котором не более одного ребра на внешней грани рисунка имеет изгиб . Этот рисунок можно построить за линейное время из 1-планарного вложения графа. [17] Одноплоскостные графы имеют ограниченную толщину книги , [18] но некоторые 1-планарные графы, включая K 2,2,2,2, имеют толщину книги не менее четырех. [19]
1-планарные графы имеют ограниченную локальную ширину дерева , что означает, что существует (линейная) функция f такая, что 1-плоские графы диаметра d имеют ширину дерева не более f ( d ); то же самое свойство в более общем случае справедливо для графов, которые можно вложить в поверхность ограниченного рода с ограниченным числом пересечений на ребро. У них также есть сепараторы — небольшие наборы вершин, удаление которых разлагает граф на компоненты связности, размер которых составляет постоянную долю размера всего графа. На основе этих свойств многочисленные алгоритмы для плоских графов, такие как метод Бейкера для разработки алгоритмов аппроксимации , могут быть расширены до 1-планарных графов. Например, этот метод приводит к схеме аппроксимации за полиномиальное время для максимального независимого набора 1-планарного графа. [20]
Обобщения и родственные концепции
[ редактировать ]Класс графов, аналогичных внешнепланарным графам для 1-планарности, называется внешне-1-планарными графами . Это графы, которые можно нарисовать на диске, с вершинами на границе диска и не более чем с одним пересечением на каждом ребре. Эти графы всегда можно нарисовать (внешне-1-планарным способом) с прямыми ребрами и пересечениями под прямым углом . [21] Используя динамическое программирование для дерева SPQR данного графа, можно проверить, является ли он внешне-1-планарным за линейное время . [22] [23] Трехсвязные компоненты графа (узлы SPQR-дерева) могут состоять только из графов циклов , графов связей и четырехвершинных полных графов , из чего также следует, что внешне-1-планарные графы плоские и имеют древовидную ширину не более трех .
К 1-планарным графам относятся графы с 4-мя картами , графы, образованные из смежностей областей на плоскости, причем в любой точке встречаются не более четырех областей. И наоборот, каждый оптимальный 1-планарный граф является графом с 4 отображениями. Однако 1-планарные графы, которые не являются оптимальными 1-планарными, не могут быть графами-картами. [24]
1-планарные графы были обобщены до k- планарных графов, графов, в которых каждое ребро пересекается не более k раз (0-планарные графы - это в точности планарные графы). Рингель определил локальное число пересечений G такое как наименьшее неотрицательное целое число k , что G имеет k -планарный рисунок. Поскольку локальное число пересечений — это максимальная степень графа пересечений ребер оптимального рисунка, а толщину (минимальное количество планарных графов, на которые можно разбить ребра) можно рассматривать как хроматическое число графа пересечений соответствующий рисунок, то из теоремы Брукса следует , что толщина не превышает единицы плюс локальное число пересечений. [25] -планарные графы k с n вершинами имеют не более O ( k 1/2 п ) края, [26] и ширина дерева O (( kn ) 1/2 ). [27] Мелкий минор -планарного графа k с глубиной d сам по себе является (2 d + 1) k -планарным графом, поэтому мелкие миноры 1-плоских графов и k -планарных графов также являются разреженными графами , подразумевая, что 1-плоские и k -планарные графы имеют ограниченное расширение . [28]
Непланарные графы также могут быть параметризованы их числом пересечений — минимальным количеством пар ребер, которые пересекаются на любом рисунке графа. Граф с номером пересечения k обязательно является k -планарным, но не обязательно наоборот. Например, граф Хивуда имеет пересечение номер 3, но нет необходимости, чтобы все три пересечения происходили на одном и том же ребре графа, поэтому он является 1-планарным и фактически может быть нарисован таким образом, который одновременно оптимизирует общее количество пересечений и количество пересечений на ребро.
Еще одно родственное понятие для непланарных графов — это асимметрия графа , минимальное количество ребер, которое необходимо удалить, чтобы сделать граф плоским.
Ссылки
[ редактировать ]- ^ Рингель, Герхард (1965), «Задача шести цветов на сфере», Статьи математического семинара Гамбургского университета (на немецком языке), 29 (1–2): 107–117, doi : 10.1007/BF02996313 , МР 0187232 , S2CID 123286264 .
- ^ Jump up to: а б Бородин, О. В. (1984), "Решение задачи Рингеля о вершинно-граничной раскраске планарных графов и раскраске 1-планарных графов", Методы дискретного анализа (41): 12–26, 108, MR 0832128 .
- ^ Альбертсон, Майкл О.; Мохар, Боян (2006), «Раскраска вершин и граней локально плоских графов» (PDF) , Graphs and Combinatorics , 22 (3): 289–295, doi : 10.1007/s00373-006-0653-4 , MR 2264852 , S2CID 1028234 .
- ^ Шумахер, Х. (1986), «О структуре 1-планарных графов», Mathematical News (на немецком языке), 125 : 291–300, doi : 10.1002/mana.19861250122 , MR 0847368 .
- ^ Чап, Юлиус; Худак, Давид (2013), «О рисунках и разложениях 1-планарных графов» , Электронный журнал комбинаторики , 20 (2), P54, doi : 10.37236/2392 .
- ^ Бранденбург, Франц Иосиф; Эппштейн, Дэвид ; Гляйснер, Андреас; Гудрич, Майкл Т .; Ханауэр, Катрин; Рейслубер, Йозеф (2013), «О плотности максимальных 1-планарных графов», в Дидимо, Уолтер; Патриньяни, Маурицио (ред.), Proc. 20-й Международный Симп. рисование графика .
- ^ Jump up to: а б Чап, Юлиус; Худак, Давид (2012), «1-планарность полных многодольных графов», Discrete Applied Mathematics , 160 (4–5): 505–512, doi : 10.1016/j.dam.2011.11.014 , MR 2876333 .
- ^ Судзуки, Юсуке (2010), «Перевложения максимальных 1-планарных графов», SIAM Journal on Discrete Mathematics , 24 (4): 1527–1540, doi : 10.1137/090746835 , MR 2746706 .
- ^ Дидимо, Уолтер (2013), «Плотность рисунков прямолинейных 1-планарных графов», Information Processing Letters , 113 (7): 236–240, doi : 10.1016/j.ipl.2013.01.013 , MR 3017985 .
- ^ Григорьев Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для встраиваемых графов с небольшим количеством пересечений на ребро» , Algorithmica , 49 (1): 1–11, doi : 10.1007/s00453-007-0010-x , hdl : 1874/17980 , МР 2344391 , S2CID 8174422 .
- ^ Коржик Владимир П.; Мохар, Боян (2009), «Минимальные препятствия для 1-погружения и твердость тестирования 1-планарности», Толлис, Иоаннис Г.; Патриньяни, Маурицио (ред.), Рисование графиков: 16-й Международный симпозиум, GD 2008, Ираклион, Крит, Греция, 21–24 сентября 2008 г., Переработанные статьи , Конспекты лекций по информатике , том. 5417, Springer, стр. 302–312, arXiv : 1110.4881 , doi : 10.1007/978-3-642-00219-9_29 , S2CID 13436158 .
- ^ Кабельо, Серджио; Мохар, Боян (2012), Добавление одного ребра к планарным графам затрудняет число пересечений и 1-планарность , arXiv : 1203.5944 , Bibcode : 2012arXiv1203.5944C . Расширенная версия статьи 17-го симпозиума ACM по вычислительной геометрии, 2010 г.
- ^ Jump up to: а б Баннистер, Майкл Дж.; Кабельо, Серджио; Эппштейн, Дэвид (2013), «Параметризованная сложность 1-планарности», Симпозиум по алгоритмам и структурам данных (WADS 2013) , arXiv : 1304.5591 , Bibcode : 2013arXiv1304.5591B , doi : 10.7155/jgaa.00457 , S2CID 4417 962 .
- ^ Эгглтон, Роджер Б. (1986), «Прямолинейные рисунки графиков», Utilitas Mathematica , 29 : 149–172, MR 0846198 .
- ^ Томассен, Карстен (1988), «Прямолинейные рисунки графиков», Журнал теории графов , 12 (3): 335–341, doi : 10.1002/jgt.3190120306 , MR 0956195 .
- ^ Хонг, Сокхи ; Идс, Питер ; Лиотта, Джузеппе; Пун, Шенг-Хунг (2012), «Теорема Фари для 1-планарных графов», в Гудмундссоне, Иоахиме; Местре, Хулиан; Виглас, Тасо (ред.), Вычисления и комбинаторика: 18-я ежегодная международная конференция, COCOON 2012, Сидней, Австралия, 20–22 августа 2012 г., Труды , конспекты лекций по информатике, том. 7434, Springer, стр. 335–346, номер документа : 10.1007/978-3-642-32241-9_29 .
- ^ Алам, штат Мэриленд Джавахерул; Бранденбург, Франц Дж.; Кобуров, Стивен Г. (2013), «Чертежи прямолинейных сеток 3-связных 1-планарных графов», Рисование графиков: 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 сентября 2013 г., Пересмотренные избранные статьи ( PDF) , Конспекты лекций по информатике, том. 8242, стр. 83–94, номер документа : 10.1007/978-3-319-03841-4_8 .
- ^ Бекос, Майкл А.; Брукдорфер, Тилль; Кауфманн, Майкл; Рафтопулу, Хризанти (2015), «1-плоские графы имеют постоянную толщину книги», Алгоритмы – ESA 2015 , Конспекты лекций по информатике, том. 9294, Springer, стр. 130–141, номер документа : 10.1007/978-3-662-48350-3_12 .
- ^ Бекос, Майкл; Кауфманн, Майкл; Зильке, Кристиан (2015), «Проблема встраивания книги с точки зрения решения SAT», Proc. 23-й международный симпозиум по рисованию графов и сетевой визуализации (GD 2015) , стр. 113–125 .
- ^ Григорьев и Бодлаендер (2007) . Григорьев и Бодлендер формулируют свои результаты только для графов с известным 1-планарным вложением и используют древовидную декомпозицию планаризации вложения с заменой пересечений вершинами четвертой степени; однако их методы прямо подразумевают ограниченную локальную ширину дерева исходного 1-планарного графа, что позволяет применять метод Бейкера непосредственно к нему, не зная вложения.
- ^ Дехкорди, Хуман Рейси; Идс, Питер (2012), «Каждый граф внешней 1-плоскости имеет рисунок пересечения под прямым углом», International Journal of Computational Geometry & Applications , 22 (6): 543–557, doi : 10.1142/S021819591250015X , MR 3042921 .
- ^ Хонг, Сок Хи ; Идс, Питер ; Като, Наоки; Лиотта, Джузеппе; Швейцер, Паскаль; Судзуки, Юсуке (2013), «Алгоритм линейного времени для проверки внешней 1-планарности», в Висмат, Стивен; Вольф, Александр (ред.), 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 8242, стр. 71–82, номер документа : 10.1007/978-3-319-03841-4_7 .
- ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж.; Гляйснер, Андреас; Ханауэр, Катрин; Нойвирт, Дэниел; Рейслубер, Йозеф (2013), «Распознавание внешних 1-планарных графов в линейном времени», в Висмат, Стивен; Вольф, Александр (ред.), 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23–25 сентября 2013 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 8242, стр. 107–118, номер документа : 10.1007/978-3-319-03841-4_10 .
- ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карта графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148 , MR 2147819 , S2CID 2657838 .
- ^ Кайнен, Пол (1973), «Толщина и грубость графиков», Abh. Математика. Сем. унив. Гамбург , 39 : 88–95, doi : 10.1007/BF02992822 , MR 0335322 , S2CID 121667358 .
- ^ Пах, Янош ; Тот, Геза (1997), «Графики, нарисованные с небольшим количеством пересечений на ребро», Combinatorica , 17 (3): 427–439, doi : 10.1007/BF01215922 , MR 1606052 , S2CID 20480170 .
- ^ Дуймович, Вида ; Эппштейн, Дэвид ; Вуд, Дэвид Р. (2015), «Род, ширина дерева и число локальных скрещиваний», Proc. 23-й Международный симпозиум по рисованию графов и сетевой визуализации (GD 2015) , стр. 77–88, arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D .
- ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Спрингер, Теорема 14.4, с. 321, номер домена : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7 , МР 2920058 .
Дальнейшее чтение
[ редактировать ]- Кобуров, Стивен; Лиотта, Джузеппе; Монтеккиани, Фабрицио (2017), «Аннотированная библиография по 1-планарности», Computer Science Review , 25 : 49–67, arXiv : 1703.02261 , Bibcode : 2017arXiv170302261K , doi : 10.1016/j.cosrev.2017.06.00 2 , S2CID 7732463