Вкладення графу

У топологічній теорії графів, вкладення (також врізання) графу $G$ у поверхню Σ — це подання графу $G$ на Σ, де точки Σ асоціюються з вершинами, а прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що:

кінцеві точки дуги, які пов'язані з ребром $e$ , є точками, пов'язаними з кінцевими вершинами дуги $e$
ніяка дуга не містить точок, асоційованих з іншими вершинами,
ніякі дві дуги не перетинаються у внутрішніх точках цих дуг.

Тут поверхня є компактним, зв'язаним 2-многовидом.

Неформально, вкладення графу в поверхню є зображенням графу на поверхні, побудоване так, що його ребра можуть перетинатися тільки в їхніх кінцевих точках. Відомо, що будь-який скінченний граф можна вкласти в 3-вимірний евклідів простір $\mathbb {R} ^{3}$ [1], а планарні графи можна вкласти у 2-вимірний евклідів простір $\mathbb {R} ^{2}$ .

Часто вкладення розглядається, як клас еквівалентності (за гомеоморфізмами Σ) представлень описаного виду.

Деякі автори дають слабшу версію визначення «вкладення графу», в якій не вимагається відсутність перетинів ребер. У цьому контексті сильніше визначення описується як «вкладення графу без перетинів».[2]

Ця стаття обговорює тільки строге визначення вкладення графу. Слабке визначення обговорюється в статтях «Візуалізація графів» і «Число схрещувань».

Термінологія

Якщо граф $G$ вкладений у замкнену поверхню Σ, то доповнення об'єднання точок і дуг, асоційованих з вершинами і ребрами графу $G$ , є сімейством областей (або граней).[3]

Двокоміркове вкладення або карта (map) — це вкладення, за якого кожна грань гомеоморфна відкритому диску.[4]

Двокоміркове замкнуте вкладення — вкладення, за якого замикання будь-якої грані гомеоморфне замкнутому диску.

Рід графу — це мінімальне ціле число n, за якого граф можна вкласти в поверхню роду n. Зокрема, планарний граф має рід 0, оскільки його можна намалювати на сфері без самоперетинів. Неорієнтований рід графу — це найменше ціле число n, таке, що граф можна вкласти в неорієнтовану поверхню (неорієнтованого) роду n.[3]

Ейлерів рід — це найменше ціле число n, за якого граф можна вкласти в орієнтовану поверхню (орієнтованого) роду n/2 або орієнтовану поверхню (неорієнтованого) роду n. Граф є орієнтовано простим, якщо його ейлерів рід менший, ніж не орієнтований рід.

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

Комбінаторне вкладення

Вкладений граф однозначно визначає циклічні порядки ребер, інцидентних тій самій вершині. Множина всіх цих циклічних порядків називається системою поворотів^{[прояснити]}. Вкладення з тієї ж самої системи поворотів вважаються еквівалентними, і відповідний клас еквівалентності вкладень називається комбінаторним вкладенням (на противагу терміну топологічне вкладення, яке стосується попереднього визначення точок і кривих). Іноді систему поворотів саму називають «комбінаторним вкладенням»[5][6][7].

Вкладений граф також визначає природні циклічні порядки ребер, які задають границі граней вкладення. Однак робота з цими гране-орієнтованими порядками менш очевидна, оскільки в деяких випадках деякі ребра можуть проходитись двічі при обході межі грані. Наприклад, це завжди так при вкладанні дерев, які мають єдину грань. Щоб подолати цю комбінаторну перешкоду, можна вважати кожне ребро «розділеним» на два «півребра» або на два «боки». При цих угодах у всіх гранях межа проходить кожне півребро тільки раз і кожне півребро одного ребра завжди проходить у протилежних напрямках.

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

Задача визначення роду графу є NP-повною (задача визначення, чи має граф з n вершинами рід g, є NP-повною).[8]

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

Перший прорив відбувся 1979 року, коли алгоритми з часовою складністю O(n^O^(g)) були незалежно представлені щорічному симпозіуму ACV з теорії обчислень: один алгоритм запропонували В. Філотті і Г. Л. Міллер, а інший — Джон Райф. Їхні підходи були повністю відмінними, але за пропозицією організаційного комітету вони представили об'єднану статтю.[9]

В 1999 році оголошено, що випадок фіксованого роду можна розв'язати за лінійний час від розміру графу і за подвійний експоненціальний час від роду[10].

Вкладення графу в простори вищих розмірностей

Відомо, що будь-який скінченний граф можна вкласти в тривимірний простір[1].

Один з методів такого вкладання — помістити точки (вершини графу) на прямій і малювати ребра як криві, що лежать в окремих півплощинах, які мають цю пряму як спільну для всіх півплощин межу. Такого роду вкладення називається книжковим вкладенням графу. Ця метафора стає зрозумілою, якщо уявити кожну півплощину у вигляді сторінки книги. Зрозуміло, що деякі ребра можна намалювати без перехрещень на одній «сторінці».

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

З іншого боку, будь-який скінченний граф можна намалювати без перетинів у тривимірному просторі з прямими ребрами шляхом розміщення вершин у загальному положенні таким чином, щоб ніякі чотири з них не були компланарними (не лежали в одній площині). Наприклад, цього можна досягти, розміщуючи i-ту вершину в точці (i, i², i³) на кривій моментів.

Вкладення графу в тривимірний простір, у якому ніякі два цикли не є топологічно зачепленими, називається незачепленим вкладенням. Граф має незачеплене вкладення тоді й лише тоді, коли він не містить жодного з семи графів петерсонового сімейства як мінора.

Див. також

Вкладення (інші види вкладень)
Двічі пов'язаний список ребер, структура даних для подання вкладення графу на площині
Тріангуляція (геометрія)
Книга (теорія графів)

Примітки

Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995). Three-dimensional graph drawing. У Tamassia, Roberto; Tollis, Ioannis G. Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer. с. 1–11. doi:10.1007/3-540-58950-3_351..
Katoh, Naoki; Tanigawa, Shin-ichi (2007). Enumerating Constrained Non-crossing Geometric Spanning Trees. Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings. Lecture Notes in Computer Science 4598. Springer-Verlag. с. 243–253. ISBN 978-3-540-73544-1. doi:10.1007/978-3-540-73545-8_25..
Gross, Jonathan; Tucker, Thomas W. (2001). Topological Graph Theory. Dover Publications. ISBN 0-486-41741-7..
Lando, Sergei K.; Zvonkin, Alexander K. (2004). Graphs on Surfaces and their Applications. Springer-Verlag. ISBN 3-540-00203-0..
Mutzel, Petra; Weiskircher, René (2000). Computing Optimal Embeddings for Planar Graphs. Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings. Lecture Notes in Computer Science 1858. Springer-Verlag. с. 95–104. ISBN 978-3-540-67787-1. doi:10.1007/3-540-44968-X_10..
Didjev, Hristo N. (1995). On drawing a graph convexly in the plane. Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer-Verlag. с. 76–83. doi:10.1007/3-540-58950-3_358..
Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010). Planar Drawings of Higher-Genus Graphs. Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag. с. 45–56. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_7..
Thomassen, Carsten (1989). The graph genus problem is NP-complete. Journal of Algorithms 10 (4): 568–576. doi:10.1016/0196-6774(89)90006-0.
Filotti, I. S.; Miller, Gary L.; Reif, John (1979). On determining the genus of a graph in O(v O(g)) steps(Preliminary Report). Proc. 11th Annu. ACM Symposium on Theory of Computing. с. 27–37. doi:10.1145/800135.804395..
Mohar, Bojan (1999). A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics 12 (1): 6–26. doi:10.1137/S089548019529248X.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[3d-gd-1] Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995). Three-dimensional graph drawing. У Tamassia, Roberto; Tollis, Ioannis G. Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer. с. 1–11. doi:10.1007/3-540-58950-3_351..

[2] Katoh, Naoki; Tanigawa, Shin-ichi (2007). Enumerating Constrained Non-crossing Geometric Spanning Trees. Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings. Lecture Notes in Computer Science 4598. Springer-Verlag. с. 243–253. ISBN 978-3-540-73544-1. doi:10.1007/978-3-540-73545-8_25..

[gt01-3] Gross, Jonathan; Tucker, Thomas W. (2001). Topological Graph Theory. Dover Publications. ISBN 0-486-41741-7..

[4] Lando, Sergei K.; Zvonkin, Alexander K. (2004). Graphs on Surfaces and their Applications. Springer-Verlag. ISBN 3-540-00203-0..

[5] Mutzel, Petra; Weiskircher, René (2000). Computing Optimal Embeddings for Planar Graphs. Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings. Lecture Notes in Computer Science 1858. Springer-Verlag. с. 95–104. ISBN 978-3-540-67787-1. doi:10.1007/3-540-44968-X_10..

[6] Didjev, Hristo N. (1995). On drawing a graph convexly in the plane. Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings. Lecture Notes in Computer Science 894. Springer-Verlag. с. 76–83. doi:10.1007/3-540-58950-3_358..

[7] Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010). Planar Drawings of Higher-Genus Graphs. Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers. Lecture Notes in Computer Science 5849. Springer-Verlag. с. 45–56. ISBN 978-3-642-11804-3. doi:10.1007/978-3-642-11805-0_7..

[8] Thomassen, Carsten (1989). The graph genus problem is NP-complete. Journal of Algorithms 10 (4): 568–576. doi:10.1016/0196-6774(89)90006-0.

[9] Filotti, I. S.; Miller, Gary L.; Reif, John (1979). On determining the genus of a graph in O(v O(g)) steps(Preliminary Report). Proc. 11th Annu. ACM Symposium on Theory of Computing. с. 27–37. doi:10.1145/800135.804395..

[10] Mohar, Bojan (1999). A linear time algorithm for embedding graphs in an arbitrary surface. SIAM Journal on Discrete Mathematics 12 (1): 6–26. doi:10.1137/S089548019529248X.