Вложение графа

Вложение графа  — изучаемое в рамках топологической теории графов представление графа $G$ на заданной поверхности $\Sigma$, в котором точки $\Sigma$ ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что:

• конечные точки дуги, ассоциированной с ребром графа $e$, являются точками, ассоциированными с конечными вершинами этого ребра графа $e$
• никакая дуга не содержит точки, ассоциированные с другими вершинами
• никакие две дуги не пересекаются во внутренних точках этих дуг.

Здесь поверхность является компактным, связным 2-мерным многообразием.

Неформально, вложение графа в поверхность является изображением графа на поверхности таким образом, что его рёбра могут пересекаться только в конечных точках. Хорошо известно, что любой конечный граф может быть вложен в трёхмерное евклидово пространство $\mathbb {R} ^{3}$, а планарные графы могут быть вложены в двумерное евклидово пространство $\mathbb {R} ^{2}$.

Часто вложение рассматривается как класс эквивалентности (по гомеоморфизмам $\Sigma$) представлений описанного вида.

В контексте проблематики визуализации графов рассматривают также слабую версию определения вложения графа, в которой не требуется отсутствие пересечений рёбер. Соответственно, сильное определение описывается как «вложение графа без пересечений».

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

Если граф $G$ вложен в замкнутую поверхность $\Sigma$, то дополнение объединения точек и дуг, ассоциированных с вершинами и рёбрами графа $G$, является семейством семейства областей (или граней). Двумерное ячеечное вложение или карта — это вложение, при котором каждая грань гомеоморфна открытому диску. Двумерное замкнутое ячеечное вложение — это вложение, при котором замыкание любой грани гомеоморфно замкнутому диску.

Укладка графа — часто используется как синоним вложения, особенно в случае планарных графов.

Род графа — это минимальное целое $n$ такое, что граф может быть вложен в поверхность рода $n$. В частности, планарный граф имеет род 0, поскольку его можно нарисовать на сфере без самопересечений. Неориентируемый род графа — это минимальное целое $n$, такое, что граф может быть вложен в неориентированную поверхность (неориентируемого) рода $n$.

Эйлеров род графа — это минимальное целое $n$, такое что граф может быть вложен в ориентируемую поверхность (ориентируемого) рода ${\tfrac {n}{2}}$ или неориентированную поверхность (неориентируемого) рода $n$. Граф является просто ориентируемым, если его эйлеров род меньше, чем неориентируемый род.

Максимальный род графа — это максимальное целое $n$, такое, что граф может быть вложен плоскоячейно (вложение плоскоячейно, если любая замкнутая кривая, не пересекающая рёбра графа, стягивается в точку) в ориентируемую поверхность рода $n$.

Комбинаторное вложение

Основная статья: Круговая система (комбинаторика)

Вложенный граф однозначно определяет циклические порядки рёбер, инцидентных той же самой вершине. Множество всех этих циклических порядков называется круговой системой. Вложения с той же самой круговой системой считаются эквивалентными, и соответствующий класс эквивалентности вложений называется комбинаторным вложением (как противоположность термину топологическое вложение, которое относится к предыдущему определению точек и кривых). Иногда круговая система сама называется «комбинаторным вложением».

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

Вычислительная сложность

Задача определения рода графа является NP-полной (задача определения, имеет ли граф с $n$ вершинами род $g$, является NP-полной).

В то же самое время задача определения рода графа является фиксированно-параметрически разрешимой, то есть известны алгоритмы с полиномиальным временем проверки, может ли граф быть вложенным в поверхность с заданным родом. То же верно и для поиска вложения.

Первый прорыв произошёл в 1979 году, когда алгоритмы с временной сложностью $O(n^{O(g)})$ были независимо доложены на ежегодном симпозиуме ACM по теории вычислений — один алгоритм предложили Ионом Филотти и Гари Миллер, а другой — Джон Райф. Их подходы были полностью отличными, но по предложению организационного комитета они представили объединённую статью.

В 1999 году показано, что случай фиксированного рода может быть решён за линейное время от размера графа и за двойное экспоненциальное время от рода.

Вложение графа в пространства больших размерностей

Известно, что любой конечный граф может быть вложен в трёхмерное пространство.

Один из методов такого вложения — поместить точки (вершины графа) на прямой и рисовать рёбра как кривые, лежащие в отдельных полуплоскостях, которые имеют эту прямую как общую для всех полуплоскостей границу. Такого рода вложение называется книжным вложением графа. Эта метафора становится понятной, если представить каждую полуплоскость в виде страницы книги. Понятно, что некоторые рёбра можно нарисовать без пересечений на одной и той же «странице». Книжной толщиной графа называется минимальное число полуплоскостей в книжном вложении.

С другой стороны, любой конечный граф можно нарисовать без пересечений в трёхмерном пространстве с прямыми рёбрами путём размещения вершин в общем положении таким образом, что никакие четыре не копланарны (не лежат в одной плоскости). Например, это можно достичь, помещая $i$-ую вершину в точку $(i,i^{2},i^{3})$ на кривой моментов.

Вложение графа в трёхмерное пространство, в котором никакие два цикла не являются топологически зацепленными, называется незацепленным вложением. Граф имеет незацепленное вложение тогда и только тогда, когда он не содержит ни одного из семи графов петерсонова семейства в качестве минора.

См. также

• Двусвязный список рёбер — структура данных для представления вложения графа в плоскости
• Правильная карта
• Теорема Фари, утверждающая, что всегда существует вложение в плоскость планарного графа, в котором все дуги представлены отрезками.

Литература

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