Embebido de Tutte

En dibujo de grafos y en teoría de grafos geométrica, un embebido de Tutte o incrustación baricéntrica de un grafo plano 3-vértices-conectado simple es un embebido de líneas rectas sin cruces con las propiedades de que la cara exterior es un polígono convexo y de que cada vértice interior está en el centroide (o baricentro) de las posiciones de sus vecinos. Si el polígono exterior es fijo, esta condición en los vértices interiores determina su posición únicamente como solución a un sistema de ecuaciones lineales. Resolver las ecuaciones geométricamente produce un embebido plano. El teorema del resorte de Tutte, probado por W. T. Tutte, 1963, establece que esta solución única siempre está libre de cruces, y como una condición más fuerte, que cada cara del embebido plano resultante es convexa.​ Se llama el teorema del resorte porque dicho embebido se puede encontrar como la posición de equilibrio para un sistema de resortes que representa los bordes del grafo.

Ejemplo

Embebido de Tutte del grafo de un cubo. Los cuatro vértices exteriores están fijos en las esquinas de un Cuadrado unidad y cada vértice restante está en el promedio de las posiciones de sus vecinos

Sea G el grafo de un cubo, y (seleccionando una de sus caras cuadriláteras como cara exterior) se fijan los cuatro vértices de la cara exterior en las cuatro esquinas de un cuadrado unidad, los puntos cuyas coordenadas x e y son las cuatro combinaciones de cero y uno.

Entonces, si los cuatro vértices restantes se colocan en los cuatro puntos cuyas coordenadas x e y son combinaciones de 1/3 y 2/3, como en la figura, el resultado será un embebido de Tutte. Porque en cada vértice interior v del embebido, y para cada una de las dos coordenadas, los tres vecinos de v tienen valores de coordenadas que son iguales a v, menores en 1/3 , y mayores en 1/3; el promedio de estos valores es el mismo que el valor de la propia coordenada de v.

Sistema de ecuaciones lineales

La condición de que un vértice v esté en el promedio de las posiciones de sus vecinos puede expresarse como dos ecuación de primer grado, una para la coordenada x de v y otro para la coordenada y de v. Para un grafo con n vértices, de los cuales h están fijos en la cara exterior, hay dos ecuaciones para cada vértice interior y también dos incógnitas (las coordenadas) para cada vértice interior. Por lo tanto, esto da un sistema de ecuaciones lineales con 2(n − h) ecuaciones y 2(n − h) incógnitas, cuya solución es un embebido de Tutte. Como mostró Tutte (1963), para grafos planos conectados con 3 vértices, este sistema no es degenerado. Por lo tanto, tiene una solución única y (con la cara exterior fija) el grafo tiene un embebido de Tutte único. Este embebido se puede encontrar en tiempo polinómico resolviendo el sistema de ecuaciones, por ejemplo, usando la eliminación de Gauss-Jordan.​

Representación poliédrica

Por el teorema de Steinitz, los grafos planos triconexos a los que se aplica el teorema del resorte de Tutte coinciden con los grafos poliédricos, los grafos formados por los vértices y las aristas de un politopo convexo. De acuerdo con la correspondencia de Maxwell–Cremona, un embebido bidimensional de un grafo plano forma la proyección vertical de un poliedro convexo tridimensional si y solo si el embebido tiene un "esfuerzo de equilibrio", una asignación de fuerzas en cada borde que afecta a ambos extremos en direcciones iguales y opuestas paralelas al borde, de modo que las fuerzas se cancelen en cada vértice. Para un embebido de Tutte, asignar a cada borde una fuerza de atracción proporcional a su longitud (como sucede en un resorte) hace que las fuerzas se cancelen en todos los vértices interiores, pero esto no genera necesariamente una tensión de equilibrio en los vértices del polígono exterior. Sin embargo, cuando el polígono exterior es un triángulo, es posible asignar fuerzas repulsivas en sus tres bordes para que las fuerzas también se cancelen allí. De esta manera, los embebidos de Tutte se pueden usar para encontrar el diagrama de Schlegel de cada politopo convexo. Por cada grafo planar de 3 conexiones G, el mismo G o el grafo dual de G tiene un triángulo, así que esto da una representación poliédrica de G o de su dual; en el caso de que el grafo dual sea el del triángulo, la conjugación permite obtener una representación poliédrica de la propia G.​

Aplicaciones en el procesamiento de geometría

En el procesamiento de geometría, el embebido de Tutte se usa para la parametrización 2D uv ${\mathcal {S}}^{*}$ de superficies 3D ${\mathcal {S}}$ más comúnmente para los casos en los que la topología de la superficie sigue siendo la misma en ${\mathcal {S}}$ y ${\mathcal {S}}^{*}$ (topología de disco). El método de Tutte minimiza la energía de distorsión total del espacio parametrizado al considerar cada vértice transformado como una masa puntual y los bordes a través de los vértices correspondientes como resortes. La tensión en cada resorte está determinada por la longitud de los bordes en la superficie 3D original para preservar su forma. Dado que es razonable tener longitudes de borde parametrizadas más pequeñas para los bordes más pequeños de ${\mathcal {S}}$ y longitudes de borde parametrizadas más grandes para los bordes más grandes de ${\mathcal {S}}$, las constantes elásticas $w_{ij}$ generalmente se toman como la inversa de la distancia absoluta entre los vértices $i,~j$ en el espacio 3D.

${\text{Energía de distorsión,}}~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}}$

donde $E({\mathcal {S}})$ representa el conjunto de aristas en la superficie 3D original. Cuando los pesos $w_{ij}$ son positivos (como es el caso anterior), se garantiza que la aplicación es biyectiva sin inversiones. Pero cuando no se aplican más restricciones, la solución que minimiza la energía de distorsión se colapsa trivialmente a un único punto en el espacio parametrizado.

Por lo tanto, se deben proporcionar condiciones de contorno donde un conjunto de vértices conocidos de la superficie 3D se asignan a puntos conocidos en el espacio parametrizado 2D. Una forma común de elegir tales condiciones de contorno es considerar los vértices en el bucle de contorno más grande de la superficie 3D original que luego se puede restringir para hacerlo corrresponder al anillo exterior de un disco unitario en el espacio parametrizado 2D. Téngase en cuenta que si la superficie 3D es una variedad, los bordes de los límites se pueden detectar verificando que pertenecen a una sola cara de la malla.

Las aplicaciones de parametrización en grafos y animación incluyen la representación de texturas, entre muchas otras.

Generalizaciones

Colin de Verdière (1991) generalizó el teorema del resorte de Tutte a grafos en superficies de género superior con curvatura no positiva, donde los bordes están representados por líneas geodésicas;​ este resultado fue posteriormente redescubierto de forma independiente por Hass y Scott (2015).​ Se probaron resultados análogos para grafos embebidos en un toroide de forma independiente por Delgado-Friedrichs (2005),​ por Gortler, Gotsman y Thurston (2006),​ y por Lovász (2019).​

Chilakamarri, Dean y Littman (1995) investigó el embebido de grafos tridimensionales de los grafos de politopos de cuatro dimensiones, formados por el mismo método que la incrustación de Tutte: eligiendo una faceta del politopo como la cara exterior de un embebido tridimensional y fijando sus vértices en su lugar como los vértices de un poliedro tridimensional en el espacio. Ahora, se debe dejar que cada vértice restante del politopo se mueva libremente en el espacio, reemplazando cada borde del politopo por un resorte. Luego, se debe encontrar la configuración de energía mínima del sistema de resortes. Como demostró, el sistema de ecuaciones obtenido de esta manera es nuevamente no degenerado, pero no está claro bajo qué condiciones este método encontrará un embebido en el que todas las facetas del politopo sean poliedros convexos.​

Resultados relacionados

El resultado de que cada grafo plano simple se puede dibujar con bordes de línea recta se llama el teorema de Fáry.​ El teorema del resorte de Tutte demuestra esto para grafos planos 3-conectados, pero el resultado es cierto de manera más general para grafos planos independientemente de su conectividad. El uso del sistema de resortes de Tutte para un grafo que no sea 3-conectado puede dar lugar a degeneraciones, en las que los subgrafos del grafo dado colapsan en un punto o un segmento de línea; sin embargo, se puede dibujar un grafo plano arbitrario utilizando el embebido de Tutte agregando bordes adicionales para hacerlo triconectado, dibujando el grafo triconectado resultante y luego eliminando los bordes adicionales.

Un grafo es k-vértices-conectado, pero no necesariamente plano, si y solo si tiene un embebido convexo en un espacio (k −1) dimensional en el que se coloca una k tupla arbitraria de vértices en los vértices de un símplex y, para cada vértice restante v, la envolvente convexa de los vecinos de v es de dimensión completa con v en su interior. Si tal embebido existe, se puede encontrar fijando las ubicaciones de los k vértices elegidos y resolviendo un sistema de ecuaciones que coloca cada vértice en el promedio de sus vecinos, tal como en el embebido plano de Tutte.​

En la generación de mallas para el método de los elementos finitos, el suavizado Laplaciano es un método común para el procesamiento posterior de una malla generada para mejorar la calidad de sus elementos.​ Este método es particularmente popular para mallas cuadriláteras, para las que otros métodos como el algoritmo de Lloyd para el suavizado de una malla triangular son menos aplicables. En este método, cada vértice se mueve hacia el promedio de las posiciones de sus vecinos, pero este movimiento solo se realiza durante un pequeño número de iteraciones, para evitar grandes distorsiones en el tamaño de los elementos o (en el caso de dominios de malla no convexa) la formación de mallas no planas entrelazadas.

Los sistemas dibujo de grafos dirigido por fuerza continúan siendo un método popular para visualizar grafos, pero estos procedimientos suelen utilizar sistemas de fuerzas más complicados que combinan fuerzas atractivas en los bordes del grafo (como en el embebido de Tutte) con fuerzas repulsivas entre pares arbitrarios de vértices. Estas fuerzas adicionales pueden hacer que el sistema tenga muchas configuraciones estables localmente en lugar de, como en el embebido de Tutte, una única solución global.​

Referencias

• Datos: Q17090559