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

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

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

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

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

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

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

Эта статья обсуждает только строгое определение вложения графа. Слабое определение обсуждается в статьях «Визуализация графов» и «Число пересечений».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Robert F. Cohen, Peter Eades, Tao Lin, Frank Ruskey (1995), "Three-dimensional graph drawing", Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer, pp. 1—11, doi:10.1007/3-540-58950-3_351{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
• Petra Mutzel, René Weiskircher (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, vol. 1858, Springer-Verlag, pp. 95—104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1
• Hristo N. Didjev (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, vol. 894, Springer-Verlag, pp. 76—83, doi:10.1007/3-540-58950-3_358
• Christian Duncan, Michael T. Goodrich, Stephen Kobourov (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, vol. 5849, Springer-Verlag, pp. 45—56, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
• Carsten Thomassen (1989), "The graph genus problem is NP-complete", Journal of Algorithms, 10 (4): 568—576, doi:10.1016/0196-6774(89)90006-0
• I. S. Filotti, Gary L. Miller, John Reif (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, pp. 27—37, doi:10.1145/800135.804395{{citation}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка)
• Bojan Mohar (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
• Jonathan Gross, Thomas W. Tucker (2001), Topological Graph Theory, Dover Publications, ISBN 0-486-41741-7
• А. К. Звонкин, С. К. Ландо. Графы на поверхностях и их приложения. — М.: МЦНМО, 2010. — ISBN 978-5-94057-588-7.
• Naoki Katoh, Shin-ichi Tanigawa (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, vol. 4598, Springer-Verlag, pp. 243—253, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1