Встраивание графа

Граф Хивуда и связанная с ним карта, встроенная в тор.

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

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

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

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

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

Некоторые авторы определяют более слабую версию определения «встраивания графа», опуская условие непересечения ребер. В таких контекстах более строгое определение описывается как «встраивание непересекающихся графов».

В этой статье рассматривается только строгое определение встраивания графов. Более слабое определение обсуждается в статьях « Рисование графика » и « Число пересечений ».

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

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

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

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

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

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

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

Основная статья: Система ротации

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

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

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

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

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

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

Первый прорыв в этом отношении произошел в 1979 году, когда были разработаны алгоритмы временной сложности O ( n ^{О ( г )} ) были независимо представлены на ежегодном симпозиуме ACM по теории вычислений : один И. Филотти и Г. Л. Миллером , а другой Джоном Рейфом . Их подходы были совершенно разными, но по предложению программного комитета они представили совместный доклад. Однако Венди Мирволд и Уильям Кокай доказали в 2011 году, что алгоритм Филотти, Миллера и Рейфа неверен.

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

Встраивание графов в многомерные пространства

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

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

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

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

Галерея

• 
  Граф Петерсена и связанная с ним карта, встроенные в проективную плоскость. Противоположные точки на окружности идентифицируются, что дает замкнутую поверхность неориентируемого рода 1.
• 
  Граф Паппуса и связанная с ним карта, встроенная в тор.
• 
  степени 7 Граф Клейна и связанное с ним отображение, встроенное в ориентируемую поверхность рода 3.

См. также

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