Номер уклона

Рисунок графика Петерсена с наклоном номер 3.

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

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

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

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

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

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

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

(еще нерешенные задачи по математике)

Существуют графы максимальной степени пять, имеющие сколь угодно большое число наклонов. Однако каждый граф максимальной степени три имеет число наклонов не более четырех; результат Wade & Chu (1994) для полного графа K ₄ показывает, что это точно. Не каждый набор из четырех наклонов подходит для рисования всех графов степени 3: набор наклонов пригоден для этой цели тогда и только тогда, когда он образует наклоны сторон и диагоналей параллелограмма . В частности, любой граф степени 3 можно нарисовать так, чтобы его ребра были либо параллельны осям, либо параллельны главным диагоналям целочисленной решетки . Неизвестно, имеют ли графы максимальной степени четыре ограниченное или неограниченное наклонное число.

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

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

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

Сложность

NP -полно определить, имеет ли граф наклон номер два. Отсюда следует, что NP-трудно определить наклонное число произвольного графа или аппроксимировать его с коэффициентом аппроксимации лучше 3/2.

Также NP-полно определить, имеет ли планарный граф планарный рисунок с наклоном номер два: сложно и экзистенциальной теории реальности определить минимальное число наклонов плоского рисунка.

Ссылки

• Барат, Янош; Матушек, Иржи ; Вуд, Дэвид Р. (2006), «Графы ограниченной степени имеют сколь угодно большую геометрическую толщину» , Electronic Journal of Combinatorics , 13 (1): R3, MR   2200531 .
• Дуймович, Вида ; Судерман, Мэтью; Вуд, Дэвид Р. (2005), «Действительно прямые графические рисунки», в Пач, Янош (ред.), Рисование графиков: 12-й Международный симпозиум, GD 2004, Нью-Йорк, Нью-Йорк, США, 29 сентября - 2 октября 2004 г., Пересмотренные избранные статьи , Конспекты лекций по информатике , том. 3383, Берлин: Springer-Verlag, стр. 122–132, arXiv : cs/0405112 , doi : 10.1007/978-3-540-31843-9_14 .
• Идс, Питер ; Хонг, Сок Хи ; Пун, Шеунг-Хунг (2010), «О прямолинейном рисовании графиков», Эппштейн, Дэвид ; Ганснер, Эмден Р. (ред.), Рисование графиков: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Пересмотренные статьи , Конспекты лекций по информатике, том. 5849, Берлин: 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), «О лемме о кольцах Родена и Салливана», Комплексные переменные, теория и применение , 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 .
• Манюх, Ян; Паттерсон, Мюррей; Пун, Шеунг-Хунг; Тачук, Крис (2011), «Сложность поиска неплоских прямолинейных изображений графиков», в Брандесе, Ульрике ; Корнельсен, Сабина (ред.), Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Гейдельберг: Springer, стр. 305–316, doi : 10.1007/978-3-642-18469-7_28 , hdl : 10281/217381 , MR   2781275 .
• Муккамала, Падмини; Сегеди, Марио (2009), «Геометрическое представление кубических графов с четырьмя направлениями», Вычислительная геометрия: теория и приложения , 42 (9): 842–851, doi : 10.1016/j.comgeo.2009.01.005 , MR   2543806 .
• Муккамала, Падмини; Палвёлдьи, Дёмётёр (2012), «Рисование кубических графов с четырьмя основными наклонами», ван Кревельд, Марк; Спекманн, Беттина (ред.), Рисование графиков: 19-й Международный симпозиум, GD 2011, Эйндховен, Нидерланды, 21–23 сентября 2011 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 7034, Springer, стр. 254–265, arXiv : 1106.1973 , doi : 10.1007/978-3-642-25878-7_25 .
• Пах, Янош ; Pálvölgyi, Dömötör (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 .
• Уэйд, Джорджия; Чу, Ж.-Х. (1994), «Рисуемость полных графов с использованием набора минимального наклона», The Computer Journal , 37 (2): 139–142, doi : 10.1093/comjnl/37.2.139 .