В топологической теории графов , A 1-планарный граф представляет собой график , который может быть обращено в евклидовой плоскости таким образом , что каждое ребро имеет не более одной точки пересечения, где он пересекает один дополнительный край. Если 1-плоский граф, одно из наиболее естественных обобщений плоских графов , нарисован таким образом, рисунок называется одноплоскостным графом или 1-планарным вложением графа .
Раскраска
1-планарные графы были впервые изучены Рингелем (1965) , который показал, что их можно раскрасить не более чем в семь цветов. [1] Позже было показано, что точное количество цветов, необходимых для раскраски этих графиков, в худшем случае, равно шести. [2] Пример полного графа K 6 , который является 1-плоским, показывает, что для 1-планарных графов иногда может потребоваться шесть цветов. Однако доказать, что шести цветов всегда достаточно, сложнее.
Мотивация Рингеля заключалась в попытке решить вариант полной раскраски для плоских графов , в котором одновременно окрашиваются вершины и грани плоского графа таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет, никакие две смежные грани не имели одинаковых цвет, и никакие смежные друг с другом вершина и грань не имеют одинаковый цвет. Очевидно, это можно сделать с использованием восьми цветов, применив теорему о четырех цветах к данному графу и его двойственному графу отдельно, используя два непересекающихся набора из четырех цветов. Однако меньшее количество цветов может быть получено путем формирования вспомогательного графа, который имеет вершину для каждой вершины или грани данного плоского графа и в котором две вершины вспомогательного графа являются смежными, если они соответствуют смежным характеристикам данного плоского графа. Вершина окраски вспомогательных графа соответствует вершине-грани окраски исходного плоского графа. Этот вспомогательный граф является 1-плоским, из чего следует, что проблема раскраски вершин-граней Рингеля также может быть решена с помощью шести цветов. [2] Граф K 6 не может быть сформирован таким образом как вспомогательный граф, но, тем не менее, проблема раскраски вершин и граней также иногда требует шести цветов; например, если раскрашиваемый плоский граф представляет собой треугольную призму , то для его одиннадцати вершин и граней требуется шесть цветов, потому что никакие три из них не могут быть окрашены в один цвет. [3]
Плотность края
Каждый 1-плоский граф с n вершинами имеет не более 4 n - 8 ребер. [4] Более того, каждый чертеж с одной плоскостью имеет не более n - 2 пересечений ; удаление одного ребра из каждой пары пересекающихся ребер оставляет плоский граф, который может иметь не более 3 n - 6 ребер, из которых сразу следует 4 n - 8 оценок количества ребер в исходном 1-плоском графе. [5] Однако, в отличие от плоских графов (для которых все максимальные плоские графы на заданном наборе вершин имеют одинаковое количество ребер друг с другом), существуют максимальные 1-плоские графы (графы, к которым нельзя добавлять дополнительные ребра при сохранении 1-планарность), у которых значительно меньше 4 n - 8 ребер. [6] Оценка 4 n - 8 максимально возможного числа ребер в 1-плоском графе может использоваться, чтобы показать, что полный граф K 7 с семью вершинами не является 1-плоским, потому что этот граф имеет 21 ребро и в данном случае 4 n - 8 = 20 <21. [7]
1-плоский граф называется оптимальным 1-плоским графом, если он имеет ровно 4 n - 8 ребер, максимально возможное. В 1-плоском вложении оптимального 1-плоского графа непересекающиеся ребра обязательно образуют четырехугольник ( многогранный граф, в котором каждая грань является четырехугольником ). Таким образом, каждая четырехугольная форма приводит к оптимальному 1-плоскому графу, добавляя две диагонали к каждой из его четырехугольных граней. Отсюда следует, что любой оптимальный 1-планарный граф эйлеров (все его вершины имеют четную степень ), что минимальная степень в таком графе равна шести и что каждый оптимальный 1-планарный граф имеет не менее восьми вершин степени ровно шесть. Кроме того, каждый оптимальный 1-плоский граф связан с четырьмя вершинами , и каждое разрезание с четырьмя вершинами в таком графе является разделяющим циклом в лежащей в основе четырехугольнике. [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] 1-планарные графы имеют ограниченную книжную толщину , [18] но некоторые 1-плоские графы, включая K 2,2,2,2, имеют книжную толщину не менее четырех. [19]
1-планарные графы имеют ограниченную локальную ширину дерева , что означает, что существует (линейная) функция f такая, что 1-планарные графы диаметра d имеют ширину дерева не более f ( d ); то же свойство имеет место в более общем случае для графов, которые могут быть вложены на поверхность ограниченного рода с ограниченным числом пересечений на ребро. У них также есть разделители , небольшие наборы вершин, удаление которых разбивает граф на связанные компоненты, размер которых составляет постоянную долю от размера всего графа. На основе этих свойств многочисленные алгоритмы для плоских графов, такие как метод Бейкера для разработки алгоритмов аппроксимации , могут быть расширены до 1-планарных графов. Например, этот метод приводит к схеме аппроксимации полинома времени для максимального независимого набора из 1-плоского графа. [20]
Класс графов, аналогичных внешнепланарным графам для 1-планарности, называется внешнепланарными графами . Это графы, которые можно нарисовать в круге, с вершинами на границе диска и не более чем с одним пересечением на каждом ребре. Эти графы всегда можно нарисовать (внешне-1-плоско) с прямыми краями и пересечениями под прямым углом . [21] Используя динамическое программирование на дереве SPQR данного графа, можно проверить, является ли он внешне-1-планарным за линейное время . [22] [23] В трехсвязной компоненте графа (узлы дерева SPQR) могут состоять только из графиков цикла , бондграфа и четыре вершинных полных графов , из которого также следует , что внешние-1-планарные графы являются плоскими и иметь ширину не более трех.
1-планарные графы включают графы с 4-мя картами, графы , сформированные из смежностей областей на плоскости, причем не более четырех областей встречаются в любой точке. И наоборот, любой оптимальный 1-плоский граф является графом с 4 отображениями. Однако 1-планарные графы, которые не являются оптимальными 1-планарными, могут не быть графами-отображениями. [24]
1-планарные графы были обобщены на k -планарные графы, графы, каждое ребро которых пересекается не более k раз (0-планарные графы - это в точности планарные графы). Рингель определил местный номер пересечения с G наименее неотрицательное целое число K такое , что G имеет K -planar чертеж. Так как номер пересечения является максимальной степенью из графа пересечений ребер оптимального рисунка, а толщина (минимальное число плоских графов , в котором ребро может быть разделены) можно рассматривать как хроматическое число точки пересечения графика соответствующий рисунок, из теоремы Брукса следует, что толщина не больше единицы плюс местное число пересечений. [25] K -planar графа с п вершинами имеет не более O ( к 1/2 п ) ребер, [26] и древесной ширина O (( кп ) 1/2 ). [27] мелкая минор из K -planar графа, с глубиной D , сам по себе является (2 г + 1) , K -planar графика, так что мелкие миноры 1-планарных графов и из K -planar графов также являются разреженными графами , откуда следует , что 1-планарный и k -планарный графы имеют ограниченное расширение . [28]
Непланарные графы также могут быть параметризованы числом их пересечений , минимальным количеством пар ребер, которые пересекаются на любом рисунке графа. Граф с номером пересечения k обязательно k -планарный, но не обязательно наоборот. Например, граф Хивуда имеет номер пересечения 3, но не обязательно, чтобы все три его пересечения происходили на одном и том же ребре графа, поэтому он является 1-плоским и фактически может быть нарисован таким образом, чтобы одновременно оптимизировать общее количество переходов и переходов на ребро.
Другая связанная концепция неплоских графов - это асимметрия графа , минимальное количество ребер, которые необходимо удалить, чтобы граф стал плоским.
Рекомендации
- ^ Рингель, Gerhard (1965), "Ein Sechsfarbenproblem Ауф дер Кугель", Abhandlungen AUS DEM Mathematischen Семинар - дер - Universität Hamburg (на немецком языке ), 29 (1-2): 107-117, DOI : 10.1007 / BF02996313 , MR 0187232 , S2CID 123286264.
- ^ а б Бородин О.В. (1984), "Решение задачи Рингеля о раскраске вершин плоских графов и раскраске 1-плоских графов", Методы Дискретного анализа (41): 12–26, 108, MR 0832128.
- ^ Альбертсон, Майкл О .; Mohar, Боян (2006), "Раскраска вершин и граней локально плоских графов" (PDF) , Графы и комбинаторика , 22 (3): 289-295, DOI : 10.1007 / s00373-006-0653-4 , MR 2264852 , S2CID 1028234.
- ^ Шумахер, H. (1986), "Zur Struktur 1-planarer графена", Mathematische Nachrichten (на немецком языке ), 125 : 291-300, DOI : 10.1002 / mana.19861250122 , MR 0847368.
- ^ Чап, Юлий; Худак, Давид (2013), «О рисунках и разложениях 1-плоских графов» , Электронный журнал комбинаторики , 20 (2), P54, doi : 10.37236 / 2392.
- ^ Бранденбург, Франц Иосиф; Эпштейн, Дэвид ; Глайсснер, Андреас; Гудрич, Майкл Т .; Ханауэр, Катрин; Рейсльхубер, Йозеф (2013), «О плотности максимальных 1-плоских графов», в Didimo, Walter; Патриньяни, Маурицио (ред.), Proc. 20-й Междунар. Symp. Рисование графика.
- ^ а б Чап, Юлий; Hudák, Дэвид (2012), "1-плоскостность полных многодольных графов", Дискретная прикладная математика , 160 (4-5): 505-512, DOI : 10.1016 / j.dam.2011.11.014 , МР 2876333.
- ^ Сузуки, Юсуке (2010), "Re-вложения максимальных 1-плоских графов", SIAM Journal по дискретной математике , 24 (4): 1527-1540, DOI : 10,1137 / 090746835 , МР 2746706.
- ^ Didimo, Вальтер (2013), "Плотность прямолинейных 1-планарных графов чертежей", Information Processing Letters , 113 (7): 236-240, DOI : 10.1016 / j.ipl.2013.01.013 , МР 3017985.
- ^ Григорьев Александр; Бодлендер, Ханс Л. (2007), «Алгоритмы для графов, встраиваемых с несколькими пересечениями на ребро», Algorithmica , 49 (1): 1–11, DOI : 10.1007 / s00453-007-0010-x , hdl : 1874/17980 , Руководство пользователя 2344391 , S2CID 8174422.
- ^ Коржик, Владимир П .; Мохар, Боян (2009), «Минимальные препятствия для 1-погружений и твердость 1-планарности», Tollis, Ioannis G .; Патриньяни, Маурицио (ред.), Рисование графиков: 16-й Международный симпозиум, GD 2008, Ираклион, Крит, Греция, 21-24 сентября 2008 г., Revised Papers , Lecture Notes in Computer Science , 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 г.
- ^ а б Баннистер, Майкл Дж .; Кабельо, Серджио; Эппштейн, Дэвид (2013), «Параметризованная сложность 1-планарности», Симпозиум по алгоритмам и структурам данных (WADS 2013) , arXiv : 1304.5591 , Bibcode : 2013arXiv1304.5591B , doi : 10.7155 / jgaa.00457 , S2CID 4417962.
- ^ Эгглтон, Роджер Б. (1986), «Прямолинейные рисунки графиков», Utilitas Mathematica , 29 : 149–172, MR 0846198.
- ^ Томасен, Карстен (1988), "Прямолинейные чертежи графов", Журнал теории графов , 12 (3): 335-341, DOI : 10.1002 / jgt.3190120306 , МР 0956195.
- ^ Хонг, Сок-Хи; Идс, Питер ; Лиотта, Джузеппе; Пун, Шеунг-Хунг (2012), «Теорема Фари для 1-плоских графов», в Gudmundsson, Joachim; Местре, Хулиан; Виглас, Тасо (ред.), Вычислительная техника и комбинаторика: 18-я ежегодная международная конференция, COCOON 2012, Сидней, Австралия, 20-22 августа 2012 г., Proceedings , Lecture Notes in Computer Science, 7434 , Springer, pp. 335–346, doi : 10.1007 / 978-3-642-32241-9_29.
- ^ Алам, штат Мэриленд Джавахерул; Бранденбург, Франц Дж .; Кобуров, Стивен Г. (2013), « Рисование на прямой сетке 3-связных 1-плоских графов», Отрисовка графика: 21-й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 сентября 2013 г., Пересмотренные избранные статьи ( PDF) , Lecture Notes в области компьютерных наук, 8242 ., С. 83-94, DOI : 10.1007 / 978-3-319-03841-4_8.
- ^ Бекос, Майкл А .; Брукдорфер, Тилль; Кауфманн, Майкл; Raftopoulou, Chrysanthi (2015), "1-планарные графы имеют постоянную толщину книги", Алгоритмы - ESA 2015 , Lecture Notes в области компьютерных наук, 9294 , Springer, С. 130-141,. DOI : 10.1007 / 978-3-662-48350 -3_12.
- ^ Бекос, Михаил; Кауфманн, Майкл; Зильке, Кристиан (2015), "Проблема вложения книг с точки зрения решения SAT", Proc. 23-й Международный симпозиум по рисованию графиков и визуализации сетей (GD 2015) , стр. 113–125..
- ^ Григорьев и Bodlaender (2007) . Григорьев и Бодлендер формулируют свои результаты только для графов с известным 1-планарным вложением и используют разложение по дереву планаризации вложения с заменами пересечений вершинами четвертой степени; однако их методы прямо подразумевают ограниченную локальную ширину дерева исходного 1-планарного графа, что позволяет применять метод Бейкера непосредственно к нему, не зная вложения.
- ^ Дехкорди, Хуман Рейси; Eades, Питер (2012), "Каждый внешний 1-плоскость граф имеет прямой угол пересечения рисунок", Международный журнал вычислительной геометрии и приложений , 22 (6): 543-557, DOI : 10.1142 / S021819591250015X , MR 3042921.
- ^ Хонг, Сок-Хи; Идс, Питер ; Като, Наоки; Лиотта, Джузеппе; Швейцер, Паскаль; Сузуки, Юсуке (2013), «Алгоритм линейного времени для проверки внешней 1-планарности», в Wismath, Стивен; Wolff, Александр (ред.), 21 - й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 сентября, 2013, пересмотренная Избранные труды , Lecture Notes в области компьютерных наук, 8242 , стр 71-82,. DOI : 10.1007 / 978- 3-319-03841-4_7.
- ^ Ауэр, Кристофер; Бахмайер, Кристиан; Бранденбург, Франц Дж .; Глайсснер, Андреас; Ханауэр, Катрин; Нойвирт, Даниэль; Рейслхубер, Йозеф (2013), «Распознавание внешних 1-плоских графов за линейное время», в Wismath, Стивен; Wolff, Александр (ред.), 21 - й Международный симпозиум, GD 2013, Бордо, Франция, 23-25 сентября, 2013, пересмотренная Избранные труды , Lecture Notes в области компьютерных наук, 8242 , стр 107-118,. DOI : 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. Математика. Сем. Univ. Гамбург , 39 : 88-95, DOI : 10.1007 / BF02992822 , MR 0335322 , S2CID 121667358.
- ^ Пах, Янош ; Тот, Геза (1997), "Графики , нарисованные несколько пересечений на краю", Combinatorica , 17 (3): 427-439, DOI : 10.1007 / BF01215922 , МР 1606052 , S2CID 20480170.
- ^ Дуймович, Вида; Эпштейн, Дэвид ; Вуд, Дэвид Р. (2015), «Род, ширина дерева и местный номер пересечения», Proc. 23-й Международный симпозиум по рисованию графиков и визуализации сетей (GD 2015) , стр. 77–88, arXiv : 1506.04380 , Bibcode : 2015arXiv150604380D.
- ^ Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , алгоритмы и комбинаторика, 28 , Springer, теорема 14.4, с. 321, DOI : 10.1007 / 978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058.
дальнейшее чтение
- Кобуров, Стивен; Лиотта, Джузеппе; Монтеккиани, Фабрицио (2017), «Аннотированная библиография по 1-планарности», Computer Science Review , 25 : 49–67, arXiv : 1703.02261 , Bibcode : 2017arXiv170302261K , doi : 10.1016 / j.cosrev.2017.06.002 , S2CID 7732463