На графике рисунка , то угловое разрешение чертежа графа является острым углом , образованный два краев , которые пересекаются в общей вершине чертежа.
Характеристики
Отношение к степени вершины
Formann et al. (1993) заметил, что каждый прямой рисунок графа с максимальной степенью d имеет угловое разрешение не более 2π / d : если v является вершиной степени d , то ребра, инцидентные v, разбивают пространство вокруг v на d клиньев с общий угол 2π , и наименьший из этих клиньев должен иметь угол не более 2π / d . Сильнее, если граф является d - регулярный , она должна иметь угловое разрешение меньше, потому что это лучшее разрешение, которое может быть достигнуто для вершины на выпуклой оболочке чертежа.
Связь с раскраской графа
Как Formann et al. (1993) показали, наибольшее возможное угловое разрешение графа G тесно связана с хроматическим числом от квадратного G 2 , график на том же множестве вершин , в котором пары вершин соединены ребром всякий раз , когда их расстояние в G является максимум два. Если G 2 можно раскрасить в χ цветов, то G можно нарисовать с угловым разрешением π / χ - ε для любого ε> 0 , назначив различные цвета вершинам правильного χ -угольника и поместив каждую вершину G рядом с к вершине многоугольника того же цвета. Используя эту конструкцию, они показали, что каждый график с максимальной степенью d имеет рисунок с угловым разрешением, пропорциональным 1 / d 2 . Эта граница близка к точной: они использовали вероятностный метод, чтобы доказать существование графов с максимальной степенью d , все рисунки которых имеют угловое разрешение..
Наличие оптимальных чертежей
Formann et al. (1993) представили пример, показывающий, что существуют графики, на которых отсутствует рисунок, обеспечивающий максимально возможное угловое разрешение; вместо этого у этих графиков есть семейство чертежей, угловое разрешение которых стремится к некоторому предельному значению, но не достигает его. В частности, они продемонстрировали граф с 11 вершинами, на котором есть чертежи с угловым разрешением π / 3 - ε для любого ε> 0 , но на нем нет чертежа с угловым разрешением точно π / 3 .
Специальные классы графов
Деревья
Каждое дерево можно нарисовать таким образом, чтобы края были равномерно распределены вокруг каждой вершины, это свойство известно как идеальное угловое разрешение . Более того, если ребра могут быть свободно переставлены вокруг каждой вершины, то такой чертеж возможен без пересечений, со всеми ребрами единичной длины или выше, и с помещением всего чертежа в ограничивающую рамку полиномиальной области . Однако, если циклический порядок ребер вокруг каждой вершины уже определен как часть входных данных проблемы, то для достижения идеального углового разрешения без пересечений иногда может потребоваться экспоненциальная площадь. [1]
Внешнепланарные графы
Идеальное угловое разрешение не всегда возможно для внешнепланарных графов , потому что вершины выпуклой оболочки чертежа со степенью больше единицы не могут иметь инцидентные ребра, равномерно распределенные вокруг них. Тем не менее, каждый внешнепланарный график максимальной степени d имеет внешнепланарный рисунок с угловым разрешением, пропорциональным 1 / d . [2]
Планарные графики
Для плоских графов с максимальной степенью d метод раскраски квадратов Formann et al. (1993) предоставляет рисунок с угловым разрешением, пропорциональным 1 / d , потому что квадрат плоского графа должен иметь хроматическое число, пропорциональное d . Точнее, Вегнер в 1977 году предположил, что хроматическое число квадрата плоского графа не превосходит, и известно, что хроматическое число не превышает . [3] Однако рисунки, полученные с помощью этой техники, обычно не являются плоскими.
Для некоторых плоских графов оптимальное угловое разрешение плоского прямолинейного чертежа составляет O (1 / d 3 ) , где d - степень графа. [4] Кроме того, на таком чертеже могут быть вынуждены использовать очень длинные края, более длинные на экспоненциальный коэффициент, чем самые короткие края на чертеже. Малиц и Папакостас (1994) использовали теорему об упаковке кругов и лемму о кольцах, чтобы показать, что каждый планарный граф с максимальной степенью d имеет плоский рисунок, угловое разрешение которого в худшем случае является экспоненциальной функцией d , независимо от количества вершин в графе.
Вычислительная сложность
NP-сложно определить, имеет ли данный график максимальной степени d рисунок с угловым разрешением 2π / d , даже в частном случае, когда d = 4 . [5] Однако для некоторых ограниченных классов рисунков, включая рисунки деревьев, в которых расширение листьев до бесконечности дает выпуклое подразделение плоскости, а также рисунки плоских графов, в которых каждая ограниченная грань представляет собой центрально-симметричный многоугольник, a рисунок оптимального углового разрешения может быть найден за полиномиальное время . [6]
История
Угловое разрешение было впервые определено Formann et al. (1993) .
Хотя изначально он был определен только для прямолинейных чертежей графов, более поздние авторы также исследовали угловое разрешение чертежей, в которых ребра представляют собой многоугольные цепи, [7] дуги окружности [8] или сплайновые кривые. [9]
Угловое разрешение графика тесно связано с его разрешением пересечения, углом, образованным пересечениями на чертеже графика. В частности, чертеж RAC стремится обеспечить, чтобы все эти углы были прямыми , т.е. максимально возможным углом пересечения. [10]
Заметки
- ^ Дункан и др. (2011) ; Halupczok & Schulz (2011) .
- ^ Малиц и Папакостас (1994) ; Гарг и Тамассия (1994) .
- ^ Крамер и Крамер (2008) ; Моллой и Салаватипур (2005) .
- ^ Garg & Tamassia (1994) .
- ^ Formann et al. (1993) ; Гарг и Тамассия (1995) .
- ^ Карлсон и Эппштейн (2007) ; Эпштейн и Вортман (2011) .
- ^ Кант (1996) ; Гутвенгер и Мутцель (1998) .
- ^ Cheng et al. (1999) ; Дункан и др. (2011) .
- ^ Брандес, Шубина и Тамассия (2000) ; Финкель и Тамассия (2005) .
- ^ Didimo, Eades & Лиотта (2009) .
Рекомендации
- Брандес, Ульрик; Шубина, Галина; Тамассия, Роберто (2000), «Улучшение углового разрешения при визуализации географических сетей», Визуализация данных 2000: Труды совместного симпозиума Eurographics и IEEE TCVG по визуализации в Амстердаме, Нидерланды, 29-31 мая 2000 г..
- Карлсон, Иосия; Эпштейн, Дэвид (2007), «Деревья с выпуклыми гранями и оптимальными углами», у Кауфманна, Михаэля; Вагнер, Доротея (ред.), Proc. 14-й Int. Symp. Графический рисунок (GD'06) , LNCS, 4372 , Springer-Verlag, стр. 77–88, arXiv : cs.CG/0607113 , doi : 10.1007 / 978-3-540-70904-6_9 , S2CID 12598338.
- Cheng, CC; Дункан, Калифорния; Goodrich, MT ; Кобоуров, С.Г. (1999), «Рисование плоских графов с дугами окружности», Рисование графов, 7-й Международный симпозиум, GD'99, Штиринский замок, Чешская Республика, 15–19 сентября 1999 г., Труды , Лекционные заметки по информатике , 1731 г. , Springer . -Verlag, стр 117-126, DOI : 10.1007 / 3-540-46648-7_12.
- Дидимо, Уолтер; Идс, Питер ; Лиотта, Джузеппе (2009), «Рисование графов с пересечениями под прямым углом», Алгоритмы и структуры данных : 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21-23 августа 2009 г. Труды , Лекционные заметки по компьютерным наукам, 5664 , стр. . 206–217, DOI : 10.1007 / 978-3-642-03367-4_19.
- Дункан, Кристиан А .; Эпштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г .; Нелленбург, Мартин (2011), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», Брандес, Ульрик; Cornelsen, Sabine (ред.), Proc. 18-й Int. Symp. Рисование графиков, конспекты лекций по информатике, 6502 , Springer-Verlag, стр. 183–194, arXiv : 1009.0581 , doi : 10.1007 / 978-3-642-18469-7_17.
- Эппштейн, Д .; Уортман, К. (2011), «Оптимальное угловое разрешение для рисунков с симметричным лицом», Журнал алгоритмов и приложений графов , 15 (4): 551–564, arXiv : 0907.5474 , doi : 10.7155 / jgaa.00238 , S2CID 10356432.
- Финкель, Бенджамин; Тамассия, Роберто (2005), «Рисование криволинейных графиков с использованием метода направленной силы», Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, 29 сентября - 2 октября 2004 г., Revised Selected Papers , Lecture Notes в области компьютерных наук, 3383 ., Springer-Verlag, стр 448-453, DOI : 10.1007 / 978-3-540-31843-9_46.
- Formann, M .; Hagerup, T .; Haralambides, J .; Кауфманн, М .; Leighton, FT ; Symvonis, A .; Welzl, E .; Woeginger, Г. (1993), "Составление графиков на плоскости с высокой разрешающей способностью ", SIAM журнал по вычислениям , 22 (5): 1035-1052, DOI : 10,1137 / 0222063 , МР 1237161.
- Гарг, Ашим; Тамассия, Роберто (1994), «Плоские чертежи и угловое разрешение: алгоритмы и границы», Алгоритмы, Второй ежегодный европейский симпозиум, Утрехт, Нидерланды, 26–28 сентября 1994 г., Труды , конспекты лекций по информатике, 855 , Springer- . Verlag, стр 12-23, DOI : 10.1007 / BFb0049393.
- Гарг, Ашим; Тамассия, Роберто (1995), «О вычислительной сложности тестирования восходящей и прямолинейной планарности», Тамассия, Роберто; Tollis, Иоаннис (ред . ), Graph Drawing , Lecture Notes в области компьютерных наук, 894 ., Springer Berlin / Heidelberg, стр 286-297, DOI : 10.1007 / 3-540-58950-3_384.
- Гутвенгер, Карстен; Mutzel, Petra (1998), «Чертежи плоских полилиний с хорошим угловым разрешением», Графическое изображение (Монреаль, Квебек, 1998) , Конспекты лекций в Comput. Наук,. 1547 , Берлин:. Springer, С. 167-182, DOI : 10.1007 / 3-540-37623-2_13 , MR 1717450.
- Халупчок, Иммануил; Шульц, Андре (2011), «Закрепление воздушных шаров с идеальными углами и оптимальной площадью», Труды 19-го Международного симпозиума по рисованию графиков.
- Кант, Г. (1996), "Рисунок планарные графы с использованием канонического упорядочения", Algorithmica , 16 (1): 4-32, DOI : 10.1007 / s004539900035 , ЛВП : 1874/16676 , МР 1394492.
- Крамер, Флорика; Kramer, Хорст (2008), "Исследование на расстоянии-раскраски графов", Дискретная математика , 308 (2-3): 422-426, DOI : 10.1016 / j.disc.2006.11.059 , MR 2378044.
- Малиц, Сет; Papakostas, Ахиллеас (1994), "О угловом разрешении плоских графов", SIAM Journal по дискретной математике , 7 (2): 172-183, DOI : 10,1137 / S0895480193242931 , МР 1271989.
- Моллой, Майкл; Salavatipour Мохаммад Р. (2005), "Оценка на хроматическом числе площади плоского графа", Журнал комбинаторной теории , Series B, 94 (2): 189-213, DOI : 10.1016 / j.jctb. 2004.12.005 , ЛВП : 1807/9473 , МР 2145512.