Введение

Подполе теории графов

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

Различные типы геометрических графиков

Планарный прямолинейный граф — это граф, в котором вершины вложены как точки в евклидовой плоскости, а рёбра — как непересекающиеся отрезки прямых. Теорема Фари утверждает, что любой планарный граф может быть представлен как планарный прямолинейный граф. Триангуляция — это планарный прямолинейный граф, к которому нельзя добавить больше рёбер, так называется потому, что каждая грань обязательно является треугольником; частным случаем является триангуляция Делоне — граф, определяемый из множества точек на плоскости путём соединения двух точек ребром, если существует окружность, содержащая только эти две точки. 1-скелет многогранника или политопа — это множество вершин и рёбер этого многогранника или политопа. Скелет любого выпуклого многогранника — планарный граф, а скелет любого k-мерного выпуклого политопа — k-связный граф. Обратно, теорема Штайница утверждает, что любой 3-связный планарный граф является скелетом выпуклого многогранника; по этой причине этот класс графов также известен как полиэдральные графы. Евклидов граф — это граф, в котором вершины представляют точки на плоскости, и каждому ребру присваивается длина, равная евклидову расстоянию между его конечными точками. Евклидово минимальное остовное дерево — это минимальное остовное дерево полного евклидова графа. Также можно определять графы по условиям на расстояния; в частности, граф единичного расстояния формируется путём соединения пар точек, находящихся на расстоянии единицы друг от друга на плоскости. Задача Хадвигера — Нельсона касается хроматического числа этих графов. Граф пересечений — это граф, в котором каждая вершина связана с множеством, и вершины соединены рёбрами, если соответствующие множества имеют непустое пересечение. Если множества являются геометрическими объектами, результатом является геометрический граф. Например, граф пересечений отрезков на одномерном пространстве — это интервальный граф; граф пересечений единичных дисков на плоскости — это граф единичных дисков. Теорема о упаковке кругов утверждает, что графы пересечений непересекающихся кругов являются точно планарными графами. Предположение Шейнермана (доказано в 2009 году) утверждает, что любой планарный граф может быть представлен как граф пересечений отрезков на плоскости. Граф Леви семейства точек и прямых имеет вершину для каждого из этих объектов и ребро для каждой пары точка-прямая, инцидентных друг другу. Графы Леви проективных конфигураций приводят ко многим важным симметричным графам и клеткам. Граф видимости замкнутого многоугольника соединяет каждую пару вершин ребром, если отрезок прямой, соединяющий вершины, полностью лежит внутри многоугольника. Неизвестно, как эффективно проверить, может ли неориентированный граф быть представлен как граф видимости. Частичный куб — это граф, вершины которого можно связать с вершинами гиперкуба таким образом, что расстояние в графе равно расстоянию Хэмминга между соответствующими вершинами гиперкуба. Многие важные семейства комбинаторных структур, такие как ациклические ориентации графа или смежности между областями в аранжировке гиперплоскостей, могут быть представлены как частичные кубические графы. Важным частным случаем частичного куба является скелет пермутоэдра — граф, в котором вершины представляют перестановки упорядоченного множества объектов, а рёбра — перестановки смежных объектов в порядке. Несколько других важных классов графов, включая медианные графы, имеют связанные определения, включающие метрические вложения. Флип-граф — это граф, образованный из триангуляций множества точек, в котором каждая вершина представляет триангуляцию, а две триангуляции соединены ребром, если они отличаются заменой одного ребра другим. Также можно определить связанные флип-графы для разбиений на четырехугольники или псевдотреугольники, а также для триангуляций более высокой размерности. Флип-граф триангуляций выпуклого многоугольника образует скелет ассоциаэдра или политопа Сташеффа. Флип-граф регулярных триангуляций множества точек (проекций выпуклых оболочек более высокой размерности) также может быть представлен как скелет так называемого вторичного политопа.