Номер наклона

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

Полные графики

Хотя тесно связанные проблемы в дискретной геометрии изучались ранее, например, Скоттом (1970) и Джеймисоном (1984), задача определения числа наклона графа была введена Уэйдом и Чу (1994), которые показали, что число наклона $n$ -вершинного полного графа $K n$ равно в точности $n$ . Рисунок с этим числом наклона можно сформировать, поместив вершины графа на правильный многоугольник .

Отношение к степени

Число наклона графа максимальной степени $d$ , очевидно, не меньше , поскольку не более двух инцидентных ребер в вершине степени $d$ могут иметь общий наклон. Точнее, число наклона не меньше линейной древесности графа, поскольку ребра одного склона должны образовывать линейный лес , а линейная древесность в свою очередь не меньше . $\lceil d/2\rceil$ $\lceil d/2\rceil$

Нерешенная задача по математике :

Имеют ли графы максимальной степени четыре ограниченное число наклонов?

(еще нерешенные проблемы по математике)

Существуют графы с максимальной степенью пять, которые имеют произвольно большое число наклонов. ^[1] Однако, каждый граф максимальной степени три имеет число наклонов не более четырех; ^[2] результат Уэйда и Чу (1994) для полного графа $K 4$ показывает, что это тесно. Не каждый набор из четырех наклонов подходит для рисования всех графов степени 3: набор наклонов подходит для этой цели тогда и только тогда, когда он образует наклоны сторон и диагоналей параллелограмма . В частности, любой граф степени 3 можно нарисовать так, чтобы его ребра были либо параллельны осям, либо параллельны главным диагоналям целочисленной решетки . [ ^3] Неизвестно, имеют ли графы максимальной степени четыре ограниченное или неограниченное число наклонов. ^[4]

Метод Кесега, Паха и Палвёлдьи (2011) для объединения упаковок кругов и квадродеревьев для достижения ограниченного числа наклонов для планарных графов с ограниченной степенью

Планарные графы

Как показали Кесег, Пач и Палвёлдьи (2011), каждый планарный граф имеет планарный прямой рисунок , в котором число различных наклонов является функцией степени графа. Их доказательство следует конструкции Малица и Папакостаса (1994) для ограничения углового разрешения планарных графов как функции степени, дополняя граф до максимального планарного графа без увеличения его степени более чем на постоянный множитель и применяя теорему об упаковке кругов для представления этого расширенного графа как набора касательных кругов. Если степень исходного графа ограничена, отношение между радиусами смежных кругов в упаковке также будет ограничено кольцевой леммой ^[5] , которая, в свою очередь, подразумевает, что использование квадродерева для размещения каждой вершины графа в точке внутри его круга даст наклоны, которые являются отношениями малых целых чисел. Количество различных наклонов, полученных с помощью этой конструкции, экспоненциально зависит от степени графа .

Сложность

Определение того, имеет ли граф наклон номер два, является NP-полной задачей . ^[6] Из этого следует, что определение наклона произвольного графа или его аппроксимация с коэффициентом аппроксимации лучше 3/2 является NP-сложной задачей.

Также NP-полной задачей является определение того, имеет ли планарный граф планарный рисунок с наклоном два ^{[7] , а для}экзистенциальной теории действительных чисел сложно определить минимальное число наклонов планарного рисунка ^{[8] .}

Примечания

^ Доказано независимо Баратом, Матоушеком и Вудом (2006) и Пачем и Палвёлдьи (2006), решив проблему, поставленную Дуймовичем, Судерманом и Вудом (2005). См. теоремы 5.1 и 5.2 Пача и Шарира (2009).
^ Mukkamala & Szegedy (2009), улучшая более ранний результат Keszegh et al. (2008); теорема 5.3 Пача и Шарира (2009).
^ Муккамала и Палвёлдьи (2012).
^ Пах и Шарир (2009).
^ Хансен (1988).
^ Форманн и др. (1993); Идс, Хонг и Пун (2010); Манюх и др. (2011).
^ Гарг и Тамассиа (2001).
^ Хоффманн (2016).

Ссылки

Барат, Янош; Матоушек, Йиржи ; Вуд, Дэвид Р. (2006), «Графы ограниченной степени имеют произвольно большую геометрическую толщину», Электронный журнал комбинаторики , 13 (1): R3, MR 2200531.
Dujmović, Vida ; Suderman, Matthew; Wood, David R. (2005), "Действительно прямые рисунки графов", в Pach, János (ред.), Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, 29 сентября - 2 октября 2004 г., Revised Selected Papers , Lecture Notes in Computer Science , т. 3383, Berlin: Springer-Verlag, стр. 122–132, arXiv : cs/0405112 , doi :10.1007/978-3-540-31843-9_14.
Eades, Peter ; Hong, Seok-Hee ; Poon, Sheung-Hung (2010), "О прямолинейном рисовании графов", в Eppstein, David ; Gansner, Emden R. (ред.), Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, 22-25 сентября 2009 г., Revised Papers , Lecture Notes in Computer Science, т. 5849, Berlin: Springer, стр. 232–243, doi : 10.1007/978-3-642-11805-0_23 , MR 2680455.
Форман, М.; Хагеруп, Т.; Хараламбидес, Дж.; Кауфман, М.; Лейтон, Ф. Т .; Симвонис, А.; Вельцль, Э .; Воегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Journal on Computing , 22 (5): 1035–1052, doi :10.1137/0222063, MR 1237161.
Гарг, Ашим; Тамассиа, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Journal on Computing , 31 (2): 601–625, doi :10.1137/S0097539794277123, MR 1861292.
Хансен, Лоуэлл Дж. (1988), «О лемме о кольце Родена и Салливана», Complex Variables, Theory and Application , 10 (1): 23–30, doi :10.1080/17476938808814284, MR 0946096.
Хоффманн, Удо (2016), «Плоское число наклона», Труды 28-й Канадской конференции по вычислительной геометрии (CCCG 2016).
Джеймисон, Роберт Э. (1984), «Плоские конфигурации, определяющие несколько наклонов», Geometriae Dedicata , 16 (1): 17–34, doi :10.1007/BF00147419, MR 0757792.
Кесег, Балаж; Пах, Янош ; Палвёлдьи, Дёмётёр (2011), «Рисование плоских графов ограниченной степени с небольшим количеством наклонов», в Брандесе, Ульрике ; Корнельсен, Сабина (ред.), Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Гейдельберг: Springer, стр. 293–304, arXiv : 1009.1315 , doi : 10.1007/978-3-642-18469-7_27, MR 2781274..
Кесег, Балаж; Пах, Янош ; Палвёлдьи, Дёмётёр; Тот, Геза (2008), «Рисование кубических графов с максимум пятью наклонами», Вычислительная геометрия: теория и приложения , 40 (2): 138–147, doi : 10.1016/j.comgeo.2007.05.003 , MR 2400539.
Малиц, Сет; Папакостас, Ахиллеас (1994), «Об угловом разрешении планарных графов», SIAM Journal on Discrete Mathematics , 7 (2): 172–183, doi :10.1137/S0895480193242931, MR 1271989.
Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), "Сложность поиска непланарных прямолинейных рисунков графов", в Brandes, Ulrik ; Cornelsen, Sabine (ред.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers , Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 305–316, doi : 10.1007/978-3-642-18469-7_28, hdl : 10281/217381 , MR 2781275.
Муккамала, Падмини; Сегеди, Марио (2009), «Геометрическое представление кубических графов с четырьмя направлениями», Computational Geometry: Theory and Applications , 42 (9): 842–851, doi : 10.1016/j.comgeo.2009.01.005 , MR 2543806.
Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), «Рисование кубических графов с четырьмя основными наклонами», в van Kreveld, Marc; Speckmann, Bettina (ред.), Graph Drawing: 19th International Symposium, GD 2011, Эйндховен, Нидерланды, 21-23 сентября 2011 г., Revised Selected Papers , Lecture Notes in Computer Science, т. 7034, Springer, стр. 254–265, arXiv : 1106.1973 , doi : 10.1007/978-3-642-25878-7_25.
Пах, Янош ; Палвёлдьи, Дёмётёр (2006), «Графы ограниченной степени могут иметь сколь угодно большие наклонные числа», Электронный журнал комбинаторики , 13 (1): N1, MR 2200545.
Пач, Янош ; Шарир, Миха (2009), «5.5 Угловое разрешение и наклоны», Комбинаторная геометрия и ее алгоритмические приложения: Лекции в Алькале , Математические обзоры и монографии, т. 152, Американское математическое общество , стр. 126–127.
Скотт, PR (1970), «О множествах направлений, определяемых $n$ точками», American Mathematical Monthly , 77 : 502–505, doi :10.2307/2317384, MR 0262933.
Уэйд, GA; Чу, Дж.-Х. (1994), «Возможность рисования полных графов с использованием минимального набора наклонов», The Computer Journal , 37 (2): 139–142, doi : 10.1093/comjnl/37.2.139.