Угловое разрешение (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Рисунок этого графа гиперкуба имеет угловое разрешение .

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

Связь со степенью вершины

[править | править код]

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

Связь с раскраской графа

[править | править код]

Как показали Форман с соавторами[1], наибольшее возможное угловое разрешение графа G тесно связано с хроматическим числом квадрата графа G2, то есть графа с тем же набором вершин, в котором каждая пара вершин соединена ребром, если расстояние между ними в графе G не превосходит двух. Если граф G2 может быть раскрашен в цветов, то G может быть нарисован с угловым разрешением для любого , если назначить различные цвета вершинам правильного -угольника и разместить каждую вершину графа G рядом с вершиной многоугольника с тем же цветом. Используя это построение, они показали, что любой граф с максимальной степенью d имеет рисунок с угловым разрешением, пропорциональным 1/d2. Эта граница близка к точной — они использовали вероятностный метод для доказательства существования графов с максимальной степенью d, все рисунки которых имеют угловое разрешение .

Существование оптимальных рисунков

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

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

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

[править | править код]

Для планарных графов с максимальной степенью d техника раскрашивания квадрата графа Формана (с соавторами)[1] даёт рисунок с угловым разрешением, пропорциональным 1/d, поскольку квадрат планарного графа должен иметь хроматическое число, пропорциональное d. Вегнер высказал в 1977 году гипотезу, что хроматическое число квадрата планарного графа не превосходит и известно, что хроматическое число не превосходит [6][7]. Однако рисунок, получающийся по этой технике, в общем случае не планарен.

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

Вычислительная сложность

[править | править код]

Задача определения, имеет ли данный граф с максимальной степенью d рисунок с угловым разрешением , NP-трудна даже в специальном случае d=4[1][8]. Однако для некоторых ограниченных классов рисунков, включая рисунки деревьев, в которых распространение листьев до бесконечности даёт выпуклое разбиение плоскости, как и рисунки планарных графов, в которых каждая ограниченная грань является центрально симметричным многоугольником, рисунок с оптимальным угловым разрешением может быть найден за полиномиальное время[9][10].

Угловое разрешение определили Форман с соавторами[1].

Хотя оно первоначально было определено для рисунков графов с прямолинейными рёбрами, позднее авторы исследовали угловое разрешение рисунков, в которых рёбра являются ломаными[11][12], дугами окружностей[13][2] или сплайнами[14][15].

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

Примечания

[править | править код]

Литература

[править | править код]
  • Ulrik Brandes, Galina Shubina, Roberto Tamassia. Improving angular resolution in visualizations of geographic networks // Data Visualization 2000: Proceedings of the Joint Eurographics and IEEE TCVG Symposium on Visualization in Amsterdam, The Netherlands, May 29-31, 2000. — 2000.
  • Josiah Carlson, David Eppstein. Trees with convex faces and optimal angles // Proc. 14th Int. Symp. Graph Drawing (GD'06) / ed:Michael Kaufmann, Dorothea Wagner. — Springer-Verlag, 2007. — Т. 4372. — С. 77–88. — (LNCS). — doi:10.1007/978-3-540-70904-6_9.
  • Cheng C. C., Duncan C. A., Goodrich M. T., Kobourov S. G. Drawing planar graphs with circular arcs // Graph Drawing, 7th International Symposium, GD'99, Štirín Castle, Czech Republic September 15–19, 1999, Proceedings. — Springer-Verlag, 1999. — Т. 1731. — С. 117–126. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-46648-7_12.
  • Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing graphs with right angle crossings // Algorithms and Data Structures: 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings. — 2009. — Т. 5664. — С. 206–217. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-03367-4_19.
  • Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, Martin Nöllenburg. Drawing trees with perfect angular resolution and polynomial area // Proc. 18th Int. Symp. Graph Drawing / Ulrik Brandes, Sabine Cornelsen. — Springer-Verlag, 2011. — Т. 6502. — С. 183–194. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-18469-7_17.
  • Eppstein D., Wortman K. Optimal angular resolution for face-symmetric drawings // Journal of Graph Algorithms and Applications. — 2011. — Т. 15, вып. 4. — С. 551–564. — doi:10.7155/jgaa.00238. — arXiv:0907.5474.
  • Benjamin Finkel, Roberto Tamassia. Curvilinear graph drawing using the force-directed method // Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers. — Springer-Verlag, 2005. — Т. 3383. — С. 448–453. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-540-31843-9_46.
  • Formann M., Hagerup T., Haralambides J., Kaufmann M., Leighton F. T., Symvonis A., Welzl E., Woeginger G. Drawing graphs in the plane with high resolution // SIAM Journal on Computing. — 1993. — Т. 22, вып. 5. — С. 1035–1052. — doi:10.1137/0222063.
  • Ashim Garg, Roberto Tamassia. Planar drawings and angular resolution: Algorithms and bounds // Algorithms, Second Annual European Symposium, Utrecht, The Netherlands, September 26–28, 1994, Proceedings. — Springer-Verlag, 1994. — Т. 855. — С. 12–23. — (Lecture Notes in Computer Science). — doi:10.1007/BFb0049393.
  • On the computational complexity of upward and rectilinear planarity testing // Graph Drawing / ed:Roberto Tamassia, Ioannis Tollis. — Springer Berlin / Heidelberg, 1995. — Т. 894. — С. 286–297. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-58950-3_384.
  • Carsten Gutwenger, Petra Mutzel. Planar polyline drawings with good angular resolution // Graph drawing (Montréal, QC, 1998). — Berlin: Springer, 1998. — Т. 1547. — С. 167–182. — (Lecture Notes in Comput. Sci.). — doi:10.1007/3-540-37623-2_13.
  • Immanuel Halupczok, André Schulz. Pinning balloons with perfect angles and optimal area // Proceedings of the 19th International Symposium on Graph Drawing. — 2011.
  • Kant G. Drawing planar graphs using the canonical ordering. — 1996. — Т. 16, вып. 1. — С. 4–32. — doi:10.1007/s004539900035.
  • Florica Kramer, Horst Kramer. A survey on the distance-colouring of graphs // Discrete Mathematics. — 2008. — Т. 308, вып. 2-3. — С. 422–426. — doi:10.1016/j.disc.2006.11.059.
  • Seth Malitz, Achilleas Papakostas. On the angular resolution of planar graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7, вып. 2. — С. 172–183. — doi:10.1137/S0895480193242931.
  • Michael Molloy, Mohammad R. Salavatipour. A bound on the chromatic number of the square of a planar graph // Journal of Combinatorial Theory. — 2005. — Т. 94, вып. 2. — С. 189–213. — doi:10.1016/j.jctb.2004.12.005.