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

В рисовании графов и геометрической теории графов или вложение Тутта барицентрическое вложение простого выпуклый , связанного с 3 вершинами , планарного графа представляет собой прямолинейное вложение без пересечений со свойствами, заключающимися в том, что внешняя грань представляет собой многоугольник и что каждая внутренняя поверхность вершина находится в среднем (или барицентре) позиций своих соседей. Если внешний многоугольник фиксирован, это условие на внутренних вершинах однозначно определяет их положение как решение системы линейных уравнений . Решение уравнений геометрическим способом дает плоское вложение . Пружинная теорема Тутте , доказанная У. Таттом ( 1963 ), утверждает, что это уникальное решение всегда не имеет пересечений, и, более того, каждая грань полученного плоского вложения выпукла. Это называется теоремой пружины, потому что такое вложение можно найти как положение равновесия для системы пружин, представляющих ребра графа.

Пример

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

Пусть G — график куба и (выбрав одну из его четырехугольных граней в качестве внешней грани) зафиксируем четыре вершины внешней грани в четырех углах единичного квадрата , точки, координаты которых x и y представляют собой все четыре комбинации. из нуля и единицы.Затем, если оставшиеся четыре вершины разместить в четырех точках, чьи координаты x и y представляют собой комбинации 1/3 и 2/3, как показано на рисунке, результатом будет вложение Тутте. Ибо в каждой внутренней вершине v вложения и для каждой из двух координат три соседа v имеют значения координат, равные v , меньшие на 1/3 и большие на 1/3; среднее значение этих значений совпадает со значением координаты самого v .

Система линейных уравнений

Условие того, что вершина v находится в среднем положении своих соседей, может быть выражено в виде двух линейных уравнений : одно для координаты x вершины v , а другое для координаты y вершины v . Для графа с n вершинами, h из которых фиксированы на внешней грани, существует два уравнения для каждой внутренней вершины, а также две неизвестные (координаты) для каждой внутренней вершины. Следовательно, это дает систему линейных уравнений с 2( n - h ) уравнениями с 2 ( n - h ) неизвестными, решением которой является вложение Тутта. Как показал Тутте (1963) , для 3-связных плоских графов эта система невырождена. Следовательно, он имеет единственное решение и (при фиксированной внешней грани) граф имеет уникальное вложение Тутта. Это вложение можно найти за полиномиальное время , решив систему уравнений, например, используя метод исключения Гаусса .

Многогранное представление

По теореме Стейница 3-связные плоские графы, к которым применяется пружинная теорема Тутте, совпадают с многогранными графами , графами, образованными вершинами и ребрами выпуклого многогранника . Согласно соответствию Максвелла-Кремоны , двумерное вложение плоского графа образует вертикальную проекцию трехмерного выпуклого многогранника тогда и только тогда, когда вложение имеет равновесное напряжение , распределение сил на каждое ребро (действующее на обе конечные точки в равных и противоположных направлениях, параллельных ребру), так что силы компенсируются в каждой вершине. Для вложения Тутте присвоение каждому ребру силы притяжения, пропорциональной его длине (например, пружины), заставляет силы компенсироваться во всех внутренних вершинах, но это не обязательно является равновесным напряжением в вершинах внешнего многоугольника. Однако, когда внешний многоугольник представляет собой треугольник, можно присвоить силы отталкивания трем его краям, чтобы и там силы компенсировались. Таким образом, вложения Тутте можно использовать для нахождения Диаграммы Шлегеля всякого выпуклого многогранника . Для каждого 3-связного плоского графа G либо сам G , либо граф двойственный к G имеет треугольник, поэтому либо это дает многогранное представление G , либо его двойственное представление; в случае, если двойственный граф — это граф с треугольником, поляризация дает многогранное представление G. самого

Приложения в обработке геометрии

При обработке геометрии встраивание Тутте используется для 2D- уф -параметризации. ${\mathcal {S}}^{*}$3D-поверхностей ${\mathcal {S}}$ чаще всего для случаев, когда топология поверхности остается одинаковой по всей длине. ${\mathcal {S}}$ и ${\mathcal {S}}^{*}$(дисковая топология). Метод Тутте минимизирует общую энергию искажения параметризованного пространства, рассматривая каждую преобразованную вершину как точечную массу, а ребра, пересекающие соответствующие вершины, как пружины. Плотность каждой пружины определяется длиной ребер исходной 3D-поверхности, чтобы сохранить форму. Поскольку разумно иметь меньшие длины параметризованных ребер для меньших ребер ${\mathcal {S}}$и большие параметризованные длины ребер для больших ребер ${\mathcal {S}}$, пружинные константы $w_{ij}$обычно принимаются как величина, обратная абсолютному расстоянию между вершинами $i,~j$ в 3D-пространстве.

${\text{Distortion Energy,}}~E=\Sigma _{(i,j)\in E({\mathcal {S}})}~w_{ij}~\|{\textbf {u}}_{\text{i}}-{\textbf {u}}_{\text{j}}\|^{2}{\text{, where }}w_{ij}={\frac {1}{\|{\textbf {v}}_{\text{i}}-{\textbf {v}}_{\text{j}}\|}}{\text{, }}\{{\textbf {u}}_{\text{i}}\}\in {\mathcal {S}}^{*}{\text{, }}\{{\textbf {v}}_{\text{i}}\}\in {\mathcal {S}}$

где $E({\mathcal {S}})$ представляет собой набор ребер исходной 3D-поверхности. Когда гири $w_{ij}$ положительны (как и в случае выше), гарантируется биективность отображения без каких-либо инверсий. Но когда никаких дополнительных ограничений не применяется, решение, которое минимизирует энергию искажения, тривиально схлопывается в одну точку параметризованного пространства.

Следовательно, необходимо обеспечить граничные условия, при которых набор известных вершин трехмерной поверхности сопоставляется с известными точками в двумерном параметризованном пространстве. Одним из распространенных способов выбора таких граничных условий является рассмотрение вершин наибольшего граничного контура исходной трехмерной поверхности, которые затем можно ограничить для отображения на внешнее кольцо единичного диска в двумерном параметризованном пространстве. Обратите внимание: если трехмерная поверхность представляет собой многообразие, граничные края можно обнаружить, проверив, что они принадлежат только одной грани сетки.

Приложения параметризации в графике и анимации включают, среди прочего, наложение текстур.

Обобщения

Колин де Вердьер (1991) обобщил пружинную теорему Тутта на графы на высшего рода поверхностях с неположительной кривизной , где ребра представлены геодезическими ; этот результат позже был независимо переоткрыт Хассом и Скоттом (2015) . Аналогичные результаты для графов, вложенных в тор, были доказаны независимо.Дельгадо -Фридрихс (2005) , Гортлер , Гоцман и Терстон (2006) , и Ловаша (2019) .

Чилакамарри, Дин и Литтман (1995) исследуют трехмерные вложения графов четырехмерных многогранников , сформированные тем же методом, что и вложение Тутта: выбирают одну грань многогранника как внешнюю грань трехмерного вложения, и зафиксируем его вершины на месте как вершины трехмерного многогранника в пространстве.Пусть каждая оставшаяся вершина многогранника сможет свободно перемещаться в пространстве, а каждое ребро многогранника замените пружиной. Затем найдите минимально-энергетическую конфигурацию системы пружин. Как они показывают, полученная таким образом система уравнений снова невырождена, но неясно, при каких условиях этот метод найдет вложение, реализующее все грани многогранника как выпуклые многогранники.

Связанные результаты

Результат, заключающийся в том, что любой простой плоский граф можно нарисовать с прямыми ребрами, называется теоремой Фари . Теорема Тутте о пружинах доказывает это для 3-связных плоских графов, но в более общем смысле этот результат верен для плоских графов независимо от связности. Использование пружинной системы Тутте для графа, который не является 3-связным, может привести к вырождениям, при которых подграфы данного графа схлопываются на точку или отрезок прямой; однако произвольный планарный граф можно нарисовать с использованием вложения Тутте, добавив дополнительные ребра, чтобы сделать его 3-связным, нарисовав получившийся 3-связный граф, а затем удалив лишние ребра.

Граф является k -вершинно-связным , но не обязательно плоским, если и только если он имеет выпуклое вложение в ( k -1)-мерное пространство, в котором произвольный k -кортеж вершин помещен в вершины симплекса и , для каждой оставшейся вершины v соседей выпуклая оболочка v полномерна с v внутри нее. Если такое вложение существует, его можно найти, зафиксировав расположение выбранных k вершин и решив систему уравнений, которая помещает каждую вершину в среднее значение ее соседей, как и в плоском вложении Тутте.

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

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