Tutte incrustación

En el dibujo de grafos y la teoría geométrica de grafos , una incrustación de Tutte o incrustación baricéntrica de un grafo planar simple , con 3 vértices conectados , es una incrustación de línea recta sin cruces con las propiedades de que la cara exterior es un polígono convexo y que cada vértice interior está en el promedio (o baricentro) de las posiciones de sus vecinos. Si el polígono exterior es fijo, esta condición sobre los vértices interiores determina su posición de forma única como la solución de un sistema de ecuaciones lineales . La resolución geométrica de las ecuaciones produce una incrustación planar . El teorema del resorte de Tutte , demostrado por WT Tutte ( 1963 ) , establece que esta solución única siempre está libre de cruces y, más fuertemente, que cada cara de la incrustación planar resultante es convexa. ^{[ 1 ]} Se llama teorema del resorte porque dicha incrustación se puede encontrar como la posición de equilibrio para un sistema de resortes que representan las aristas del grafo. 

Sea G el grafo de un cubo, y (seleccionando una de sus caras cuadriláteras como cara exterior) fijemos los cuatro vértices de la cara exterior en las cuatro esquinas de un cuadrado unitario , los puntos cuyas coordenadas x e y son todas 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á una incrustación de Tutte. Porque, en cada vértice interior v de la incrustación, 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 igual al valor de la coordenada de v mismo.

La condición de que un vértice v se encuentre en la posición promedio de sus vecinos puede expresarse como dos ecuaciones lineales , una para la coordenada x de v y otra para la coordenada y de v . Para un grafo con n vértices, h de los cuales están fijos en la cara exterior, existen 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 como resultado un sistema de ecuaciones lineales con 2( n − h ) ecuaciones en 2( n − h ) incógnitas, cuya solución es una incrustación de Tutte. Como demostró Tutte (1963) , para grafos planares con 3 vértices conexos, este sistema no es degenerado. Por lo tanto, tiene una solución única y (con la cara exterior fija) el grafo tiene una incrustación de Tutte única. Esta incrustación puede hallarse en tiempo polinomial resolviendo el sistema de ecuaciones, por ejemplo, mediante la eliminación gaussiana . ^{[ 2 ]}        

Según el teorema de Steinitz , los grafos planares 3-conexos 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 poliedro convexo . De acuerdo con la correspondencia de Maxwell-Cremona , una incrustación bidimensional de un grafo planar forma la proyección vertical de un poliedro convexo tridimensional si y solo si la incrustación tiene una tensión de equilibrio , una asignación de fuerzas a cada arista (que afectan a ambos extremos en direcciones iguales y opuestas paralelas a la arista) tal que las fuerzas se cancelan en cada vértice. Para una incrustación de Tutte, asignar a cada arista una fuerza atractiva proporcional a su longitud (como un resorte) hace que las fuerzas se cancelen en todos los vértices interiores, pero esto no es 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 a sus tres aristas para que las fuerzas también se cancelen allí. De esta forma, las incrustaciones de Tutte se pueden usar para encontrar diagramas de Schlegel de cada poliedro convexo . Para cada grafo planar 3-conexo G , o bien G mismo o el grafo dual de G tiene un triángulo, por lo que esto da una representación poliédrica de G o de su dual; en el caso de que el grafo dual sea el que tiene el triángulo, la polarización da una representación poliédrica de G mismo. ^{[ 2 ]}

En el procesamiento geométrico, se utiliza la incrustación de Tutte para la parametrización uv 2D.${\displaystyle {\mathcal {S}}^{*}}$de superficies 3D${\displaystyle {\mathcal {S}}}$más comúnmente para los casos en los que la topología de la superficie permanece igual en todo momento${\displaystyle {\mathcal {S}}}$y${\displaystyle {\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 las aristas que atraviesan los vértices correspondientes como resortes. La tensión de cada resorte está determinada por la longitud de las aristas en la superficie 3D original para preservar la forma. Dado que es razonable tener longitudes de arista parametrizadas más pequeñas para las aristas más pequeñas de${\displaystyle {\mathcal {S}}}$y longitudes de borde parametrizadas más grandes para los bordes más grandes de${\displaystyle {\mathcal {S}}}$, las constantes elásticas${\displaystyle w_{ij}}$Por lo general, se toman como el inverso de la distancia absoluta entre los vértices.${\displaystyle i,~j}$en el espacio 3D.

${\displaystyle {\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}}}$

dónde${\displaystyle E({\mathcal {S}})}$representa el conjunto de aristas en la superficie 3D original. Cuando los pesos${\displaystyle w_{ij}}$Si son positivos (como en 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 reduce trivialmente a un único punto en el espacio parametrizado.

Por lo tanto, es necesario proporcionar condiciones de contorno donde un conjunto de vértices conocidos de la superficie 3D se mapeen a puntos conocidos en el espacio parametrizado 2D. Una forma común de elegir dichas condiciones de contorno es considerar los vértices del bucle de contorno más grande de la superficie 3D original, que luego se pueden restringir para que se mapeen al anillo exterior de un disco unitario en el espacio parametrizado 2D. Cabe señalar que si la superficie 3D es una variedad, los bordes del contorno se pueden detectar verificando que pertenezcan a una sola cara de la malla.

Entre las muchas aplicaciones de la parametrización en gráficos y animación se incluye el mapeo de texturas.

También se pueden considerar incrustaciones de Tutte con pesos positivos en las aristas, donde cada vértice interior es el promedio ponderado de las posiciones de sus vecinos. ^{[ 3 ]} Orick, Stephenson y Collins (2017) formulan el problema de determinar los centros de los círculos en una representación de empaquetamiento de círculos de un grafo planar, dados los radios de los círculos, como una incrustación de Tutte ponderada, con pesos calculados a partir de los radios dados. Escriben que, si bien la cara exterior de su incrustación no es necesariamente convexa, como se requeriría para las pruebas de la corrección de las incrustaciones de Tutte, "el método aún funciona en la práctica". ^{[ 4 ]}

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 las aristas están representadas por geodésicas ; ^{[ 5 ]} este resultado fue redescubierto independientemente más tarde por Hass y Scott (2015) . ^{[ 6 ]} Resultados análogos para grafos incrustados en un toro fueron demostrados independientemente por Delgado-Friedrichs (2005) , ^{[ 7 ]} por Gortler, Gotsman y Thurston (2006) , ^{[ 8 ]} y por Lovász (2019) . ^{[ 9 ]}

Chilakamarri, Dean y Littman (1995) investigan incrustaciones de grafos tridimensionales de los grafos de politopos de cuatro dimensiones , formadas por el mismo método que la incrustación de Tutte: eligen una faceta del politopo como la cara exterior de una incrustación tridimensional y fijan sus vértices como los vértices de un poliedro tridimensional en el espacio. Dejan que cada vértice restante del politopo se mueva libremente en el espacio y reemplazan cada arista del politopo por un resorte. Luego, encuentran la configuración de energía mínima del sistema de resortes. Como muestran, el sistema de ecuaciones obtenido de esta manera es nuevamente no degenerado, pero no está claro bajo qué condiciones este método encontrará una incrustación que realice todas las facetas del politopo como poliedros convexos. ^{[ 10 ]}

El resultado de que todo grafo planar simple puede dibujarse con aristas de línea recta se conoce como el teorema de Fáry . ^{[ 11 ]} El teorema del resorte de Tutte lo demuestra para grafos planares 3-conexos, pero el resultado es válido de forma más general para grafos planares independientemente de su conectividad. El uso del sistema de resortes de Tutte para un grafo que no es 3-conexo puede dar lugar a degeneraciones, en las que subgrafos del grafo dado colapsan en un punto o un segmento de línea; sin embargo, un grafo planar arbitrario puede dibujarse utilizando la incrustación de Tutte añadiendo aristas adicionales para hacerlo 3-conexo, dibujando el grafo 3-conexo resultante y luego eliminando las aristas adicionales.

Un grafo es k -conexo por vértices , pero no necesariamente planar, si y solo si tiene una incrustación convexa en un espacio ( k - 1)-dimensional en el que una k - tupla arbitraria de vértices se coloca en los vértices de un simplex y, para cada vértice restante v , la envoltura convexa de los vecinos de v es de dimensión completa con v en su interior. Si existe tal incrustación, 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 la incrustación planar de Tutte. ^{[ 12 ]}  

En la generación de mallas de elementos finitos , el suavizado laplaciano es un método común para el postprocesamiento de una malla generada con el fin de mejorar la calidad de sus elementos; ^{[ 13 ]} es particularmente popular para mallas cuadriláteras , para las cuales otros métodos como el algoritmo de Lloyd para el suavizado de mallas triangulares son menos aplicables. En este método, cada vértice se mueve hacia o cerca del promedio de las posiciones de sus vecinos, pero este movimiento se realiza solo durante un pequeño número de iteraciones, para evitar grandes distorsiones en los tamaños de los elementos o (en el caso de dominios de malla no convexos) mallas no planas enredadas.

Los sistemas de dibujo de grafos dirigidos por fuerzas siguen siendo un método popular para visualizar grafos, pero estos sistemas suelen utilizar sistemas de fuerzas más complejos que combinan fuerzas atractivas en las aristas del grafo (como en la incrustación de Tutte) con fuerzas repulsivas entre pares arbitrarios de vértices. Estas fuerzas adicionales pueden provocar que el sistema tenga muchas configuraciones localmente estables en lugar de, como en la incrustación de Tutte, una única solución global. ^{[ 14 ]}