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

У топологічній теорії графів, вкладення (також врізання) графа $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.

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

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

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

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

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

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

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

В 1999 році оголошено, що випадок фіксованого роду можна розв'язати за лінійний час від розміру графа і за подвійний експоненціальний час^[en] від роду^[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, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.
↑ ^а ^б 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, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
↑ 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, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
↑ 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

[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, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.

[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, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.

[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, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.

[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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]