Угловое разрешение (графическое построение)
Самый острый угол между ребрами в вершине
Этот рисунок графика гиперкуба имеет угловое разрешение π/4 .

При рисовании графов угловое разрешение рисунка графа — это самый острый угол, образованный любыми двумя ребрами, которые встречаются в общей вершине рисунка.

Характеристики

Отношение к степени вершины

Форман и др. (1993) заметили, что каждое прямолинейное изображение графа с максимальной степенью d имеет угловое разрешение не более 2π/ d : если v — вершина степени d , то ребра, инцидентные v, разбивают пространство вокруг v на d клиньев с общим углом 2π , и наименьший из этих клиньев должен иметь угол не более 2π/ d . Более строго, если граф является d - регулярным , он должен иметь угловое разрешение меньше , потому что это наилучшее разрешение, которого можно достичь для вершины на выпуклой оболочке рисунка. π г − 1 {\displaystyle {\frac {\pi }{d-1}}}

Отношение к раскраске графа

Как показали Форман и др . (1993), максимально возможное угловое разрешение графа G тесно связано с хроматическим числом квадрата G 2 , графа на одном и том же множестве вершин, в котором пары вершин соединены ребром, если их расстояние в G не превышает двух. Если G 2 можно раскрасить в χ цветов, то G можно нарисовать с угловым разрешением π/ χ  − ε , для любого ε > 0 , назначив различные цвета вершинам правильного χ -угольника и поместив каждую вершину G близко к вершине многоугольника с тем же цветом. Используя эту конструкцию, они показали, что каждый граф с максимальной степенью d имеет рисунок с угловым разрешением, пропорциональным 1/ d 2 . Эта граница близка к строгой: они использовали вероятностный метод для доказательства существования графов с максимальной степенью d , все рисунки которых имеют угловое разрешение . О ( бревно ⁡ г г 2 ) {\displaystyle O\left({\frac {\log d}{d^{2}}}\right)}

Наличие оптимальных чертежей

Форман и др. (1993) привели пример, показывающий, что существуют графы, не имеющие рисунка, достигающего максимально возможного углового разрешения; вместо этого эти графы имеют семейство рисунков, угловые разрешения которых стремятся к некоторому предельному значению, не достигая его. В частности, они продемонстрировали граф с 11 вершинами, имеющий рисунки с угловым разрешением π/3 − ε для любого ε > 0 , но не имеющий рисунка с угловым разрешением точно π/3 .

Специальные классы графов

Деревья

Каждое дерево может быть нарисовано таким образом, что ребра будут равномерно распределены вокруг каждой вершины, свойство, известное как идеальное угловое разрешение . Более того, если ребра могут свободно переставляться вокруг каждой вершины, то такое рисование возможно без пересечений, со всеми ребрами единичной длины или выше, и со всем рисунком, помещающимся в ограничивающий прямоугольник полиномиальной площади . Однако, если циклическое упорядочение ребер вокруг каждой вершины уже определено как часть входных данных для задачи, то достижение идеального углового разрешения без пересечений может иногда потребовать экспоненциальной площади. [1]

Внешнепланарные графы

Идеальное угловое разрешение не всегда возможно для внешнепланарных графов , поскольку вершины на выпуклой оболочке рисунка со степенью больше единицы не могут иметь свои инцидентные ребра, равномерно расположенные вокруг них. Тем не менее, каждый внешнепланарный граф максимальной степени d имеет внешнепланарный рисунок с угловым разрешением, пропорциональным 1/ d . [2]

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

Для планарных графов с максимальной степенью d техника раскраски квадратов Формана и др. (1993) обеспечивает рисунок с угловым разрешением, пропорциональным 1/ d , поскольку квадрат планарного графа должен иметь хроматическое число, пропорциональное d . Точнее, Вегнер предположил в 1977 году, что хроматическое число квадрата планарного графа не превышает , и известно, что хроматическое число не превышает . [3] Однако рисунки, полученные с помощью этой техники, обычно не являются планарными. макс ( г + 5 , 3 г 2 + 1 ) {\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)} 5 г 3 + О ( 1 ) {\displaystyle {\frac {5d}{3}}+O(1)}

Для некоторых планарных графов оптимальное угловое разрешение плоского прямолинейного рисунка равно O(1/ d 3 ) , где d — степень графа. [4] Кроме того, такой рисунок может быть вынужден использовать очень длинные ребра, длиннее на экспоненциальный множитель, чем самые короткие ребра в рисунке. Малиц и Папакостас (1994) использовали теорему об упаковке кругов и лемму о кольцах, чтобы показать, что каждый планарный граф с максимальной степенью d имеет планарный рисунок, угловое разрешение которого в худшем случае является экспоненциальной функцией d , независимо от количества вершин в графе.

Сложность вычислений

NP-трудно определить, имеет ли заданный граф максимальной степени d рисунок с угловым разрешением 2π/ d , даже в частном случае, когда d = 4 . [5] Однако для некоторых ограниченных классов рисунков, включая рисунки деревьев, в которых расширение листьев до бесконечности создает выпуклое подразделение плоскости, а также рисунки планарных графов, в которых каждая ограниченная грань является центрально-симметричным многоугольником, рисунок с оптимальным угловым разрешением может быть найден за полиномиальное время . [6]

История

Угловое разрешение впервые было определено Форманом и др. (1993).

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

Угловое разрешение графика тесно связано с его разрешением пересечения, углом, образованным пересечениями на рисунке графика. В частности, рисунок RAC стремится обеспечить, чтобы все эти углы были прямыми углами , наибольшим возможным углом пересечения. [10]

Примечания

  1. ^ Дункан и др. (2011); Халупчок и Шульц (2011).
  2. ^ Малиц и Папакостас (1994); Гарг и Тамассия (1994).
  3. ^ Крамер и Крамер (2008); Моллой и Салаватипур (2005).
  4. ^ Гарг и Тамассиа (1994).
  5. ^ Форманн и др. (1993); Гарг и Тамассия (1995).
  6. ^ Карлсон и Эппштейн (2007); Эппштейн и Вортман (2011).
  7. ^ Кант (1996); Гутвенгер и Мутцель (1998).
  8. ^ Ченг и др. (1999); Дункан и др. (2011).
  9. ^ Брандес, Шубина и Тамассия (2000); Финкель и Тамассия (2005).
  10. ^ Дидимо, Идс и Лиотта (2009).

Ссылки

  • Брандес, Ульрик ; Шубина, Галина; Тамассиа, Роберто (2000), «Улучшение углового разрешения при визуализации географических сетей», Визуализация данных 2000: Труды совместного симпозиума Eurographics и IEEE TCVG по визуализации в Амстердаме, Нидерланды, 29–31 мая 2000 г., doi : 10.1007/978-3-7091-6783-0_3, ISBN 9783211835159.
  • Карлсон, Джосайя; Эппштейн, Дэвид (2007), «Деревья с выпуклыми гранями и оптимальными углами», в Кауфманн, Майкл; Вагнер, Доротея (ред.), Proc. 14th Int. Symp. Graph Drawing (GD'06) , LNCS, т. 4372, Springer-Verlag, стр.  77–88 , arXiv : cs.CG/0607113 , doi :10.1007/978-3-540-70904-6_9, ISBN 978-3-540-70903-9, S2CID  12598338.
  • Cheng, CC; Duncan, CA; Goodrich, MT ; Kobourov, SG (1999), "Рисование планарных графов с помощью дуг окружности", Рисование графов, 7-й Международный симпозиум, GD'99, Замок Штирина, Чешская Республика, 15–19 сентября 1999 г., Труды , Заметки лекций по информатике , т. 1731, Springer-Verlag, стр.  117–126 , doi : 10.1007/3-540-46648-7_12 , ISBN 978-3-540-66904-3.
  • Didimo, Walter; Eades, Peter ; Liotta, Giuseppe (2009), "Рисование графов с прямыми угловыми пересечениями", Алгоритмы и структуры данных : 11-й Международный симпозиум, WADS 2009, Банф, Канада, 21-23 августа 2009 г. Труды , Lecture Notes in Computer Science, т. 5664, стр.  206–217 , doi :10.1007/978-3-642-03367-4_19, ISBN 978-3-642-03366-7.
  • Дункан, Кристиан А.; Эппштейн, Дэвид ; Гудрич, Майкл Т .; Кобуров, Стивен Г.; Нёлленберг, Мартин (2011), «Рисование деревьев с идеальным угловым разрешением и полиномиальной площадью», в Брандес, Ульрик; Корнельсен, Сабина (ред.), Proc. 18th Int. Symp. Graph Drawing , Lecture Notes in Computer Science, т. 6502, Springer-Verlag, стр.  183–194 , arXiv : 1009.0581 , doi :10.1007/978-3-642-18469-7_17, ISBN 978-3-642-18468-0.
  • Эппштейн, Д.; Вортман, К. (2011), «Оптимальное угловое разрешение для гранесимметричных рисунков», Журнал графовых алгоритмов и приложений , 15 (4): 551–564 , arXiv : 0907.5474 , doi : 10.7155/jgaa.00238, S2CID  10356432.
  • Финкель, Бенджамин; Тамассиа, Роберто (2005), «Рисование криволинейного графика с использованием метода направленной силы», Рисование графа, 12-й Международный симпозиум, GD 2004, Нью-Йорк, штат Нью-Йорк, США, 29 сентября - 2 октября 2004 г., Пересмотренные избранные статьи , Lecture Notes in Computer Science, т. 3383, Springer-Verlag, стр.  448–453 , doi : 10.1007/978-3-540-31843-9_46 , ISBN 978-3-540-24528-5.
  • Форман, М.; Хагеруп, Т.; Хараламбидес, Дж.; Кауфман, М.; Лейтон, Ф. Т .; Симвонис, А.; Вельцль, Э .; Воегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Journal on Computing , 22 (5): 1035–1052 , doi :10.1137/0222063, MR  1237161.
  • Гарг, Ашим; Тамассиа, Роберто (1994), «Планарные чертежи и угловое разрешение: алгоритмы и границы», Алгоритмы, Второй ежегодный европейский симпозиум, Утрехт, Нидерланды, 26–28 сентября 1994 г., Труды , Заметки лекций по информатике, т. 855, Springer-Verlag, стр.  12–23 , doi :10.1007/BFb0049393, ISBN 978-3-540-58434-6.
  • Гарг, Ашим; Тамассиа, Роберто (1995), «О вычислительной сложности проверки восходящей и прямолинейной планарности», в Тамассиа, Роберто; Толлис, Иоаннис (ред.), Рисование графов , Lecture Notes in Computer Science, т. 894, Springer Berlin / Heidelberg, стр.  286–297 , doi : 10.1007/3-540-58950-3_384 , ISBN 978-3-540-58950-1.
  • Гутвенгер, Карстен; Мютцель, Петра (1998), «Планарные полилинейные рисунки с хорошим угловым разрешением», Graph drawing (Монреаль, Квебек, 1998) , Lecture Notes in Comput. Sci., т. 1547, Берлин: Springer, стр.  167–182 , doi :10.1007/3-540-37623-2_13, ISBN 978-3-540-65473-5, МР  1717450.
  • Халупчок, Иммануэль; Шульц, Андре (2011), «Закрепление воздушных шаров с идеальными углами и оптимальной площадью», Труды 19-го Международного симпозиума по рисованию графов.
  • Кант, Г. (1996), «Рисование планарных графов с использованием канонического порядка», Algorithmica , 16 (1): 4– 32, doi : 10.1007/s004539900035, hdl : 1874/16676 , MR  1394492.
  • Крамер, Флорика; Крамер, Хорст (2008), «Обзор дистанционной раскраски графов», Дискретная математика , 308 ( 2–3 ): 422–426 , doi :10.1016/j.disc.2006.11.059, MR  2378044.
  • Малиц, Сет; Папакостас, Ахиллеас (1994), «Об угловом разрешении планарных графов», SIAM Journal on Discrete Mathematics , 7 (2): 172– 183, doi :10.1137/S0895480193242931, MR  1271989.
  • Моллой, Майкл; Салаватипур, Мохаммад Р. (2005), «Граница хроматического числа квадрата планарного графа», Журнал комбинаторной теории , Серия B, 94 (2): 189–213 , doi : 10.1016/j.jctb.2004.12.005, hdl : 1807/9473 , MR  2145512.
Получено с "https://en.wikipedia.org/w/index.php?title=Угловое_разрешение_(графический_рисунок)&oldid=1268627771"