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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

С другой стороны, любой конечный граф можно нарисовать без пересечений в трёхмерном пространстве с прямыми рёбрами путём размещения вершин в общем положении таким образом, что никакие четыре не копланарны (не лежат в одной плоскости). Например, это можно достичь, помещая ${\displaystyle i}$ -ую вершину в точку ${\displaystyle (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. — ( ). — doi : .
• 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 : .
• Hristo N. Didjev. . — Springer-Verlag, 1995. — Т. 894. — С. 76–83. — (Lecture Notes in Computer Science). — doi : .
• Christian Duncan, Michael T. Goodrich, Stephen Kobourov. Planar Drawings of Higher-Genus Graphs // . — Springer-Verlag, 2010. — Т. 5849. — С. 45–56. — (Lecture Notes in Computer Science). — ISBN 978-3-642-11804-3 . — doi : .
• Carsten Thomassen. The graph genus problem is NP-complete // Journal of Algorithms. — 1989. — Т. 10 , вып. 4 . — С. 568–576 . — doi : .
• I. S. Filotti, Gary L. Miller, John Reif. On determining the genus of a graph in O(v O(g)) steps(Preliminary Report) // . — 1979. — С. 27–37. — doi : .
• Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface // . — 1999. — Т. 12 , вып. 1 . — С. 6–26 . — doi : .
• Jonathan Gross, Thomas W. Tucker. . — 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. — ( ). — ISBN 978-3-540-73544-1 . — doi : .