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

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

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

Повні графи

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

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

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

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

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

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

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

Складність

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

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

Примітки

1. Wade, Chu, 1994.
2. Довели незалежно Барат, Матоушек, Вуд (Barát, Matoušek, Wood, (2006)) і Пах, Палвелді (Pach, Pálvölgyi, (2006)), коли розв'язували задачу, яку поставив Дуймович, Судерман і Шарір (Dujmović, Suderman, Wood, (2005)). Див. теореми 5.1 і 5.2 у Паха і Шаріра (Pach, Sharir, (2009)).
3. Муккамала, Сегеді (Mukkamala, Szegedy, (2009)), які покращили раніший результат Кезега, Палвелді, Тота (Keszegh, Pach, Pálvölgyi, Tóth, (2008)). Див. теорему 5.3 у Паха і Шаріра (Pach, Sharir, (2009)).
4. Mukkamala, Pálvölgyi, 2012.
5. Pach, Sharir, 2009.
6. Keszegh, Pach, Pálvölgyi, 2011.
7. Hansen, 1988.
8. Formann, Hagerup, Haralambides, Kaufmann, 1993.
9. Eades, Hong, Poon, 2010.
10. Maňuch, Patterson, Poon, Thachuk, 2011.
11. Garg, Tamassia, 2001.

Література

• János Barát, Jiří Matoušek, David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness // . — 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. — () — 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 // . — 1993. — Т. 22, вип. 5. — С. 1035–1052. — DOI:10.1137/0222063.
• Ashim Garg, Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing // . — 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 // . — 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 // . — 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 // . — 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 // . — 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 // . — 1994. — Т. 37, вип. 2. — С. 139–142. — DOI:10.1093/comjnl/37.2.139.