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

Вложение графа в топологическое пространство, часто евклидово

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

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

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

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

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

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

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

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

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

Если граф вложен в замкнутую поверхность , то дополнение объединения точек и дуг, связанных с вершинами и ребрами, представляет собой семейство областей (или граней ). ^[3] Вложение 2-клеток , клеточное вложение или отображение — это вложение, в котором каждая грань гомеоморфна открытому диску. ^[4] Замкнутое вложение 2-клеток — это вложение, в котором замыкание каждой грани гомеоморфно замкнутому диску. ${\displaystyle G}$ ${\displaystyle \Sigma }$ ${\displaystyle G}$

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

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

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

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

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

Вложенный граф однозначно определяет циклические порядки ребер, инцидентных одной и той же вершине. Набор всех этих циклических порядков называется системой вращения . Вложения с одной и той же системой вращения считаются эквивалентными, а соответствующий класс эквивалентности вложений называется комбинаторным вложением (в отличие от термина топологическое вложение , который относится к предыдущему определению в терминах точек и кривых). Иногда сама система вращения называется «комбинаторным вложением». ^{[5] [6] [7]}

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

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

Сложность вычислений

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

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

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

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

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

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

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

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

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

Галерея

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

Смотрите также

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

Ссылки

1. Cohen, Robert F.; Eades, Peter ; Lin, Tao; Ruskey, Frank (1995), "Трехмерное рисование графов", в Tamassia, Roberto ; Tollis, Ioannis G. (ред.), Рисование графов: Международный семинар DIMACS, GD '94 Princeton, New Jersey, USA, 10–12 октября 1994 г., Труды , Заметки лекций по информатике , т. 894, Springer, стр. 1–11, doi : 10.1007/3-540-58950-3_351 , ISBN 978-3-540-58950-1.
2. Като, Наоки; Танигава, Син-ичи (2007), «Перечисление ограниченных непересекающихся геометрических остовных деревьев», Computing and Combinatorics, 13-я ежегодная международная конференция, COCOON 2007, Банф, Канада, 16-19 июля 2007 г., Труды , Lecture Notes in Computer Science , т. 4598, Springer-Verlag, стр. 243–253, CiteSeerX 10.1.1.483.874 , doi :10.1007/978-3-540-73545-8_25, ISBN  978-3-540-73544-1.
3. Гросс, Джонатан; Такер, Томас В. (2001), Топологическая теория графов , Dover Publications, ISBN 978-0-486-41741-7.
4. Ландо, Сергей К.; Звонкин, Александр К. (2004), Графы на поверхностях и их приложения , Springer-Verlag, ISBN 978-3-540-00203-1.
5. Мутцель, Петра ; Вайскирхер, Рене (2000), «Вычисление оптимальных вложений для планарных графов», Computing and Combinatorics, 6-я ежегодная международная конференция, COCOON 2000, Сидней, Австралия, 26–28 июля 2000 г., Труды , 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. Диджев, Христо Н. (1995), «О рисовании выпуклого на плоскости графика», Рисование графа, Международный семинар DIMACS, GD '94, Принстон, Нью-Джерси, США, 10–12 октября 1994 г., Труды , Заметки лекций по информатике, т. 894, Springer-Verlag, стр. 76–83, doi : 10.1007/3-540-58950-3_358 , ISBN 978-3-540-58950-1.
7. Дункан, Кристиан; Гудрич, Майкл Т.; Кобуров, Стивен (2010), «Планарные рисунки графов высшего рода», Рисование графов, 17-й международный симпозиум, GD 2009, Чикаго, Иллинойс, США, 22–25 сентября 2009 г., Пересмотренные статьи , Заметки лекций по информатике, т. 5849, Springer-Verlag, стр. 45–56, arXiv : 0908.1608 , doi :10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
8. Томассен, Карстен (1989), «Проблема определения рода графа является NP-полной», Журнал алгоритмов , 10 (4): 568–576, doi :10.1016/0196-6774(89)90006-0
9. Филотти, И. С.; Миллер, Гэри Л .; Рейф, Джон (1979), «Определение рода графа за O(v O(g)) шагов (Предварительный отчет)», Труды 11-го ежегодного симпозиума ACM по теории вычислений , стр. 27–37, doi : 10.1145/800135.804395.
10. Myrvold, Wendy ; Kocay, William (1 марта 2011 г.). «Ошибки в алгоритмах встраивания графов». Журнал компьютерных и системных наук . 2 (77): 430–438. doi :10.1016/j.jcss.2010.06.002.
11. Мохар, Боян (1999), «Линейный алгоритм времени для встраивания графов в произвольную поверхность», SIAM Journal on Discrete Mathematics , 12 (1): 6–26, CiteSeerX 10.1.1.97.9588 , doi :10.1137/S089548019529248X