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

---

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

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

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

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

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

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

---