Кутова роздільність (теорія графів)

Кутова́ розді́льність малюнка графа стосується найгострішого кута, утвореного будь-якими двома ребрами, які зустрічаються в одній вершині малюнка.

Малюнок цього графа гіперкуба має кутову роздільність ${\displaystyle \pi /4}$.

Властивості

Зв'язок зі степенем вершини

Форман зі співавторами помітили, що будь-який малюнок графа з ребрами-відрізками з найбільшим степенем d має кутову роздільність, що не перевищує ${\displaystyle 2\pi /d}$ — якщо v є вершиною зі степенем d, то ребра, інцидентні v, розбивають простір навколо вершини v на d клинів зі сумарним кутом ${\displaystyle 2\pi }$, а найменший із цих клинів повинен мати кут, що не перевищує ${\displaystyle 2\pi /d}$. Строгіше, якщо граф є d-регулярним, він повинен мати кутову роздільність, меншу від ${\displaystyle {\frac {\pi }{d-1}}}$, оскільки це найкраща роздільність, яку можна отримати для вершини на опуклій оболонці малюнка.

Зв'язок із розфарбуванням графа

Як показали Форман зі співавторами , найбільша можлива кутова роздільність графа G тісно пов'язана із хроматичним числом квадрата графа G² тобто графа з тим самим набором вершин, у якому кожна пара вершин з'єднана ребром, якщо відстань між ними у графі G не перевищує двох. Якщо граф G² можна розфарбувати в ${\displaystyle \chi }$ кольорів, то G можна намалювати з кутовою роздільністю ${\displaystyle \pi /\chi -\epsilon }$ для будь-кого ${\displaystyle \epsilon >0}$, якщо призначити різні кольори вершинам правильного ${\displaystyle \chi }$-кутника і розмістити кожну вершину графа G поруч із вершиною многокутника з тим самим кольором. Використовуючи цю побудову, вони показали, що будь-який граф з найбільшним степенем d має малюнок із кутовою роздільністю, пропорційною1/d². Ця межа близька до точної — вони використовували ймовірнісний метод для доведення існування графів з найбільшим степенем d, всі малюнки яких мають кутову роздільність ${\displaystyle O\left({\frac {\log d}{d^{2}}}\right)}$.

Існування оптимальних малюнків

Форман зі співавторами навели приклад, що показує, що існують графи, які не мають малюнків з найбільшою можливою кутовою роздільністю. Навпаки, ці графи мають сімейство малюнків, кутові роздільності яких прямують до деякого обмеженого значення, але не досягають його. Конкретно, вони представили граф із 11 вершинами, який має малюнок із кутовою роздільністю ${\displaystyle \pi /3-\epsilon }$ для будь-кого ${\displaystyle \epsilon >0}$, але не має малюнка з кутовою роздільністю, точно рівною ${\displaystyle \pi /3}$.

Окремі класи графів

Дерева

Будь-яке дерево можна намалювати так, щоб ребра виявились рівномірно розподіленими навколо кожної вершини, — властивість, відома як досконала кутова роздільність. Більше того, якщо ребра навколо кожної з вершин можна вільно переставляти, то такий малюнок можливий без перетинів з ребрами завдовжки одиниця або більше, а також весь малюнок міститься у прямокутнику поліноміальної площі. Однак, якщо циклічне впорядкування ребер навколо кожної вершини вже задано як частину умови задачі, отримання кутової роздільності без перетинів може іноді вимагати експоненціальної площі.

Зовніпланарні графи

Досконала кутова роздільність не завжди можлива для зовніпланарних графів, оскільки вершина на опуклій оболонці малюнка зі степенем, більшим від одиниці, не може мати інцидентних їй ребер, рівномірно розподілених навколо вершини. Проте будь-який зовніпланарний граф з найбільшим степенем d має зовніпланарний малюнок з кутовою роздільністю, пропорційною1/d.

Планарні графи

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

Для деяких планарних графів оптимальна кутова роздільність планарного малюнка з ребрами у вигляді відрізків дорівнює O(1/d³), де d є степенем графа. Крім того, такі малюнки можуть вимушено мати дуже довгі ребра, довші, ніж експоненційний множник від найкоротшого ребра малюнка. Маліц і Папакостас використали , щоб показати, що будь-який планарний граф з найбільшим степенем d має планарний малюнок, кутова роздільність якого в гіршому випадку є експоненційною функцією від d і яка залежить від числа вершин графа.

Обчислювальна складність

Задача визначення, чи має граф з найбільшим степенем d малюнок з кутовою роздільністю ${\displaystyle 2\pi /d}$, NP-складна навіть у частковому випадку d=4. Однак для деяких обмежених класів малюнків, зокрема для малюнків дерев, у яких поширення листя до нескінченності дає опукле розбиття площини, як і малюнки планарних графів, у яких кожна обмежена грань є центральносиметричним многокутником, рисунок з оптимальною кутовою роздільністю можна знайти за поліноміальний час.

Історія

Кутову роздільність ввели Форман зі співавторами.

Хоча її спочатку визначено для малюнків графів із прямолінійними ребрами, пізніше автори досліджували кутову роздільність малюнків, на яких ребра є ламаними, дугами кіл або сплайнами.

Кутова роздільність графа тісно пов'язана з його роздільністю схрещень, тобто, кутами, утвореними схрещеннями на малюнку графа. Зокрема, під час малювання графів із прямими кутами шукають подання, яке забезпечує, щоб усі ці кути були прямими, що є найбільшим можливим кутом перетину.

Примітки

1. Formann, Hagerup, Haralambides и др., 1993.
2. Duncan, Eppstein, Goodrich и др., 2011.
3. Halupczok, Schulz, 2011.
4. Malitz, Papakostas, 1994.
5. Garg, Tamassia, 1994.
6. Kramer, Kramer, 2008.
7. Molloy, Salavatipour, 2005.
8. Garg, Tamassia, 1995.
9. Carlson, Eppstein, 2007.
10. Eppstein, Wortman, 2011.
11. Kant, 1996.
12. Gutwenger, Mutzel, 1998.
13. Cheng, Duncan, Goodrich, Kobourov, 1999.
14. Brandes, Shubina, Tamassia, 2000.
15. Finkel, Tamassia, 2005.
16. Didimo, Eades, Liotta, 2009.

Література

• 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. — () — DOI:10.1007/3-540-46648-7_12.
• Walter Didimo, Peter Eades, Giuseppe Liotta. Drawing graphs with right angle crossings // : 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 // . — 2011. — Т. 15, вип. 4. — С. 551–564. — arXiv:0907.5474. — DOI:10.7155/jgaa.00238.
• 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 // . — 1993. — Т. 22, вип. 5. — С. 1035–1052. — DOI:10.1137/0222063.
• Ashim Garg, Roberto Tamassia. Planar drawings and angular resolution: Algorithms and bounds // . — 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 // . — 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 // . — 2005. — Т. 94, вип. 2. — С. 189–213. — (Series B). — DOI:10.1016/j.jctb.2004.12.005.