Номер откоса - Slope number

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

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

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

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

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

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

Нерешенная проблема в математике: Имеют ли графики максимальной четвертой степени ограниченное число наклона? (больше нерешенных задач по математике)

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

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

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

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

Сложность

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

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

Примечания

1. Независимо доказано Барат, Матушек и Вуд (2006) и Пах и Палвёльдьи (2006), решение проблемы, поставленной Дуймович, Suderman & Wood (2005). См. Теоремы 5.1 и 5.2 из Пах и Шарир (2009).
2. Муккамала и Сегеди (2009), улучшая предыдущий результат Keszegh et al. (2008); теорема 5.3 из Пах и Шарир (2009).
3. Муккамала и Палвёльдьи (2012).
4. Пах и Шарир (2009).
5. Хансен (1988).
6. Formann et al. (1993); Идс, Хонг и Пун (2010); Maňuch et al. (2011).
7. Гарг и Тамассия (2001).
8. Хоффманн (2016).

Рекомендации

• Барат, Янош; Матушек, Иржи; Вуд, Дэвид Р. (2006), «Графы ограниченной степени имеют сколь угодно большую геометрическую толщину», Электронный журнал комбинаторики, 13 (1): R3, МИСТЕР  2200531.
• Дуймович, Вида; Судерман, Мэтью; Вуд, Дэвид Р. (2005), «Действительно прямые графические рисунки», в Пах, Янош (ред.), Графический рисунок: 12-й Международный симпозиум, GD 2004, Нью-Йорк, Нью-Йорк, США, 29 сентября - 2 октября 2004 г., пересмотренные избранные доклады, Конспект лекций по информатике, 3383, Берлин: Springer-Verlag, стр. 122–132, arXiv:cs / 0405112, Дои:10.1007/978-3-540-31843-9_14.
• Идс, Питер; Хонг, Сок-Хи; Пун, Шеунг-Хунг (2010), «О прямолинейном рисовании графиков», в Эппштейн, Дэвид; Ганснер, Эмден Р. (ред.), Графический рисунок: 17-й Международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22-25 сентября 2009 г., Исправленные статьи, Конспект лекций по информатике, 5849, Берлин: Springer, стр. 232–243, Дои:10.1007/978-3-642-11805-0_23, МИСТЕР  2680455.
• Formann, M .; Hagerup, T .; Haralambides, J .; Кауфманн, М .; Лейтон, Ф. Т.; Symvonis, A .; Вельцль, Э.; Вегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Журнал по вычислениям, 22 (5): 1035–1052, Дои:10.1137/0222063, МИСТЕР  1237161.
• Гарг, Ашим; Тамассия, Роберто (2001), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», SIAM Журнал по вычислениям, 31 (2): 601–625, Дои:10.1137 / S0097539794277123, МИСТЕР  1861292.
• Хансен, Лоуэлл Дж. (1988), "О лемме Родена и Салливана о кольцах", Комплексные переменные, теория и применение, 10 (1): 23–30, Дои:10.1080/17476938808814284, МИСТЕР  0946096.
• Хоффманн, Удо (2016), «Число плоского уклона», Труды 28-й Канадской конференции по вычислительной геометрии (CCCG 2016).
• Джеймисон, Роберт Э. (1984), «Плоские конфигурации, определяющие несколько уклонов», Geometriae Dedicata, 16 (1): 17–34, Дои:10.1007 / BF00147419, МИСТЕР  0757792.
• Кесег, Балаж; Пах, Янош; Pálvölgyi, Dömötör (2011), «Рисование плоских графов ограниченной степени с небольшими наклонами», Брандес, Ульрик; Корнельсен, Сабина (ред.), Графический рисунок: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., отредактированные избранные статьи, Конспект лекций по информатике, 6502, Heidelberg: Springer, стр. 293–304, arXiv:1009.1315, Дои:10.1007/978-3-642-18469-7_27, МИСТЕР  2781274.
• Кесег, Балаж; Пах, Янош; Палвёльдьи, Дёмётёр; Тот, Геза (2008), «Рисование кубических графиков с максимум пятью наклонами», Вычислительная геометрия: теория и приложения, 40 (2): 138–147, Дои:10.1016 / j.comgeo.2007.05.003, МИСТЕР  2400539.
• Малиц, Сет; Папакостас, Ахиллеас (1994), "Об угловом разрешении плоских графов", Журнал SIAM по дискретной математике, 7 (2): 172–183, Дои:10.1137 / S0895480193242931, МИСТЕР  1271989.
• Mauch, Ján; Паттерсон, Мюррей; Пун, Шеунг-Хунг; Тачук, Крис (2011), «Сложность поиска неплоских прямолинейных чертежей графов», Брандес, Ульрик; Корнельсен, Сабина (ред.), Графический рисунок: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., отредактированные избранные статьи, Конспект лекций по информатике, 6502, Heidelberg: Springer, стр. 305–316, Дои:10.1007/978-3-642-18469-7_28, HDL:10281/217381, МИСТЕР  2781275.
• Муккамала, Падмини; Сегеди, Марио (2009), «Геометрическое представление кубических графов с четырьмя направлениями», Вычислительная геометрия: теория и приложения, 42 (9): 842–851, Дои:10.1016 / j.comgeo.2009.01.005, МИСТЕР  2543806.
• Муккамала, Падмини; Палвёльдьи, Дёмётёр (2012), «Рисование кубических графиков с четырьмя основными наклонами», Ван Кревельд, Марк; Спекманн, Беттина (ред.), Графический рисунок: 19-й Международный симпозиум, GD 2011, Эйндховен, Нидерланды, 21-23 сентября 2011 г., отредактированные избранные статьи, Конспект лекций по информатике, 7034, Springer, стр. 254–265, arXiv:1106.1973, Дои:10.1007/978-3-642-25878-7_25.
• Пах, Янош; Палвёльдьи, Дёмётёр (2006), «Графы ограниченной степени могут иметь сколь угодно большие числа наклона», Электронный журнал комбинаторики, 13 (1): N1, МИСТЕР  2200545.
• Пах, Янош; Шарир, Миха (2009), «5.5 Угловое разрешение и наклоны», Комбинаторная геометрия и ее алгоритмические приложения: лекции по Алкале, Математические обзоры и монографии, 152, Американское математическое общество, стр. 126–127.
• Скотт П. Р. (1970), "О множествах направлений, определяемых п точки", Американский математический ежемесячный журнал, 77: 502–505, Дои:10.2307/2317384, МИСТЕР  0262933.
• Wade, G.A .; Чу, Ж.-Х. (1994), "Возможность рисования полных графов с использованием минимального набора наклонов", Компьютерный журнал, 37 (2): 139–142, Дои:10.1093 / comjnl / 37.2.139.