Геометрическая теория графов в более широком смысле — это большая и аморфная подобласть теории графов , занимающаяся графами, определяемыми геометрическими средствами. В более строгом смысле геометрическая теория графов изучает комбинаторные и геометрические свойства геометрических графов, то есть графов, нарисованных на евклидовой плоскости с возможно пересекающимися прямолинейными ребрами , и топологических графов , где ребрам разрешено быть произвольными непрерывными кривыми, соединяющими вершины ; таким образом, ее можно описать как «теорию геометрических и топологических графов» (Pach 2013). Геометрические графы также известны как пространственные сети .
Планарный прямолинейный граф — это граф, в котором вершины вложены как точки в евклидовой плоскости , а ребра вложены как непересекающиеся отрезки . Теорема Фари утверждает, что любой планарный граф может быть представлен как планарный прямолинейный граф. Триангуляция — это планарный прямолинейный граф, к которому нельзя добавить больше ребер, называемый так потому, что каждая грань обязательно является треугольником; частным случаем этого является триангуляция Делоне , граф, определяемый из набора точек на плоскости путем соединения двух точек ребром всякий раз, когда существует окружность, содержащая только эти две точки.
1- скелет многогранника или политопа — это множество вершин и ребер указанного многогранника или политопа. Скелет любого выпуклого многогранника является планарным графом, а скелет любого k - мерного выпуклого многогранника является k -связным графом . Наоборот, теорема Штейница утверждает, что любой 3-связный планарный граф является скелетом выпуклого многогранника; по этой причине этот класс графов также известен как многогранные графы .
Евклидов граф — это граф, в котором вершины представляют точки на плоскости, а каждому ребру назначена длина, равная евклидову расстоянию между его конечными точками. Евклидово минимальное остовное дерево — это минимальное остовное дерево евклидова полного графа . Также возможно определять графы условиями на расстояния; в частности, граф единичных расстояний образуется путем соединения пар точек, которые находятся на единичном расстоянии друг от друга на плоскости. Проблема Хадвигера–Нельсона касается хроматического числа этих графов.
Граф пересечений — это граф, в котором каждая вершина связана с множеством и в котором вершины соединены ребрами всякий раз, когда соответствующие множества имеют непустое пересечение. Когда множества являются геометрическими объектами, результатом является геометрический граф. Например, граф пересечений отрезков прямых в одном измерении является интервальным графом ; граф пересечений единичных кругов на плоскости является графом единичных кругов . Теорема об упаковке кругов утверждает, что графы пересечений непересекающихся кругов являются в точности планарными графами. Гипотеза Шейнермана (доказанная в 2009 году) утверждает, что каждый планарный граф может быть представлен как граф пересечений отрезков прямых на плоскости.
Граф Леви семейства точек и прямых имеет вершину для каждого из этих объектов и ребро для каждой инцидентной пары точка-прямая. Графы Леви проективных конфигураций приводят ко многим важным симметричным графам и клеткам .
Граф видимости замкнутого многоугольника соединяет каждую пару вершин ребром всякий раз, когда отрезок прямой, соединяющий вершины, целиком лежит в многоугольнике. Неизвестно, как эффективно проверить, может ли неориентированный граф быть представлен как граф видимости.
Частичный куб — это граф, вершины которого могут быть связаны с вершинами гиперкуба таким образом, что расстояние в графе равно расстоянию Хэмминга между соответствующими вершинами гиперкуба. Многие важные семейства комбинаторных структур, такие как ациклические ориентации графа или смежности между областями в расположении гиперплоскости , могут быть представлены как частичные кубические графы. Важным частным случаем частичного куба является скелет пермутоэдра , графа, в котором вершины представляют собой перестановки набора упорядоченных объектов, а ребра представляют собой обмены объектов, смежных в порядке. Несколько других важных классов графов, включая медианные графы, имеют связанные определения, включающие метрические вложения (Bandelt & Chepoi 2008).
Флип -граф — это граф, образованный из триангуляций множества точек, в котором каждая вершина представляет триангуляцию, а две триангуляции соединены ребром, если они отличаются заменой одного ребра на другое. Также можно определить связанные флип-графы для разбиений на четырехугольники или псевдотреугольники, а также для триангуляций более высокой размерности. Флип-граф триангуляций выпуклого многоугольника образует скелет ассоциаэдра или многогранника Сташеффа . Флип-граф регулярных триангуляций множества точек (проекции выпуклых оболочек более высокой размерности) также может быть представлен как скелет, так называемого вторичного многогранника .
Медиа, связанные с геометрической теорией графов на Wikimedia Commons