Число нахилів графа

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

Малюнок графа Петерсена з числом нахилів 3

Повні графи

Хоча близькі задачі комбінаторної геометрії вивчали й раніше (Скотт у 1970 і Джемісон у 1984), задачу визначення числа нахилів графа поставили Вейд і Чу, показавши, що число нахилів графа з $n$ вершинами повного графа $K_{n}$ дорівнює рівно $n$. Малюнок графа з таким числом нахилів можна отримати, розташувавши вершини графа в кутах правильного многокутника.

Зв'язок зі степенем графа

Зрозуміло, що число нахилів графа з найбільшим степенем $d$ не менше $\lceil d/2\rceil$, оскільки максимум два інцидентні ребра вершини степеня d можуть лежати на одній прямій (мати один нахил). Точніше, число нахилів не менше лінійної деревності графа, оскільки ребра одного нахилу мають утворювати лінійний ліс, а лінійна деревність, у свою чергу, не менша ніж $\lceil d/2\rceil$.

Існують графи з найбільшим степенем 5, що мають довільно велике число нахилів. Однак будь-який граф із найбільшим степенем 3 має не більше чотирьох нахилів. Результат Вейда і Чу (Wade, Chu, (1994)) для повного графа $K_{4}$ показує, що ця межа точна. Не будь-який набір із чотирьох нахилів підходить для малювання всіх графів степеня 3 — набір нахилів підходить для малювання тоді й лише тоді, коли вони є нахилами сторін та діагоналей паралелограма. Зокрема, будь-який граф степеня 3 можна намалювати так, що його ребра або паралельні осям, або паралельні основним діагоналям цілочисельної ґратки. Невідомо, чи обмежене число нахилів графів з найбільшим степенем 4.

Метод Кезега, Паха та Палвелді комбінування пакування кіл і дерева квадрантів для отримання обмеженого числа нахилів для планарних графів з обмеженим степенем

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

Як показали Кезег, Пах і Палвелді (Keszegh, Pach, Pálvölgyi, (2011)), будь-який планарний граф має плоский малюнок у вигляді прямих відрізків, у якому число різних нахилів є функцією від степеня графа. Їхнє доведення ґрунтується на побудові Малиця і Папакостаса (Malitz, Papakostas, (1994)) для обмеження кутової роздільності планарних графів як функції степеня. Степінь обмежують доповненням графа до максимального планарного графа без збільшення його степеня більш ніж на сталий множник, а потім застосовують теорема про упаковку кіл для подання цього розширеного графа як набору кіл, що дотикаються між собою. Якщо степінь початкового графа обмежено, відношення радіусів суміжних кіл у пакуванні буде також обмеженим, звідки, у свою чергу, випливає, що застосування дерева квадрантів для всіх вершин графа в точці всередині кола дає нахили, які є відношеннями малих цілих чисел. Число різних нахилів, що отримується при цій побудові, є експонентою від степеня графа.

Складність

Визначення, чи дорівнює число нахилів 2, є NP-повною задачею. Звідси випливає, що NP-складною задачею є визначення числа нахилів довільного графа або апроксимація цього числа з гарантованою ефективністю, кращою за 3/2.

Перевірка, чи можна зобратити планарний граф планарним малюнком із числом нахилів 2, також є NP-повною задачею.

Література

• János Barát, Jiří Matoušek, David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness // Electronic Journal of Combinatorics. — 2006. — Т. 13, вип. 1. — С. R3.
• Vida Dujmović, Matthew Suderman, David R. Wood. Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers / János Pach. — Berlin : Springer-Verlag, 2005. — Т. 3383. — С. 122–132. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-31843-9_14.
• Peter Eades, Seok-Hee Hong, Sheung-Hung Poon. Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers / David Eppstein, Emden R. Gansner. — Berlin : Springer, 2010. — Т. 5849. — С. 232–243. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-11805-0_23.
• M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, F. T. Leighton, A. Symvonis, E. Welzl, G. J. Woeginger. 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. On the computational complexity of upward and rectilinear planarity testing // SIAM Journal on Computing. — 2001. — Т. 31, вип. 2. — С. 601–625. — DOI:10.1137/S0097539794277123.
• Lowell J. Hansen. On the Rodin and Sullivan ring lemma // Complex Variables, Theory and Application. — 1988. — Т. 10, вип. 1. — С. 23–30. — DOI:10.1080/17476938808814284.
• Robert E. Jamison. Planar configurations which determine few slopes // Geometriae Dedicata. — 1984. — Т. 16, вип. 1. — С. 17–34. — DOI:10.1007/BF00147419.
• Balázs Keszegh, János Pach, Dömötör Pálvölgyi. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — Heidelberg : Springer, 2011. — Т. 6502. — С. 293–304. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_27.
• Balázs Keszegh, János Pach, Dömötör Pálvölgyi, Géza Tóth. Drawing cubic graphs with at most five slopes // Computational Geometry: Theory and Applications. — 2008. — Т. 40, вип. 2. — С. 138–147. — DOI:10.1016/j.comgeo.2007.05.003.
• 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.
• Ján Maňuch, Murray Patterson, Sheung-Hung Poon, Chris Thachuk. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. — Heidelberg : Springer, 2011. — Т. 6502. — С. 305–316. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-18469-7_28.
• Padmini Mukkamala, Mario Szegedy. Geometric representation of cubic graphs with four directions // Computational Geometry: Theory and Applications. — 2009. — Т. 42, вип. 9. — С. 842–851. — DOI:10.1016/j.comgeo.2009.01.005.
• Padmini Mukkamala, Dömötör Pálvölgyi. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. — Springer, 2012. — Т. 7034. — С. 254–265. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-25878-7_25.
• János Pach, Dömötör Pálvölgyi. Bounded-degree graphs can have arbitrarily large slope numbers // Electronic Journal of Combinatorics. — 2006. — Т. 13, вип. 1. — С. N1.
• János Pach, Micha Sharir. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. — American Mathematical Society, 2009. — Т. 152. — С. 126–127. — (Mathematical Surveys and Monographs)
• P. R. Scott. On the sets of directions determined by n points // American Mathematical Monthly. — 1970. — Т. 77. — С. 502–505. — DOI:10.2307/2317384.
• G. A. Wade, J.-H. Chu. Drawability of complete graphs using a minimal slope set // The Computer Journal. — 1994. — Т. 37, вип. 2. — С. 139–142. — DOI:10.1093/comjnl/37.2.139.