Embebido de Tutte
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.
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.
[1] 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.
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.
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.
[2] 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.
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í.
más comúnmente para los casos en los que la topología de la superficie sigue siendo la misma en
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
generalmente se toman como la inversa de la distancia absoluta entre los vértices
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.
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.
[4] Se probaron resultados análogos para grafos embebidos en un toroide de forma independiente por Delgado-Friedrichs (2005),[5] por Gortler, Gotsman y Thurston (2006),[6] y por Lovász (2019).
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.
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.
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.
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.
