Todas las incrustaciones

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 plano simple , conexo por 3 vértices , es una incrustación de línea recta libre de 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 en los vértices interiores determina su posición de forma única como la solución a un sistema de ecuaciones lineales . Resolver las ecuaciones geométricamente produce una incrustación plana . El teorema del resorte de Tutte , demostrado por WT Tutte (1963), establece que esta solución única siempre es libre de cruces y, con mayor fuerza, que cada cara de la incrustación plana 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 los bordes del grafo.

Ejemplo

Sea G la gráfica 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 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á 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 el mismo que el valor de coordenadas de v mismo.

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 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 posición 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 en 2( n − h ) incógnitas, cuya solución es una incrustación de Tutte. Como Tutte (1963) mostró, para grafos planares conexos 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 una incrustación de Tutte única. Esta incrustación se puede encontrar en tiempo polinomial resolviendo el sistema de ecuaciones, por ejemplo, utilizando la eliminación gaussiana . ^[2]

Representación poliédrica

Según el teorema de Steinitz , los grafos planares 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 poliedro convexo . Según 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 afecta a ambos puntos finales en direcciones iguales y opuestas paralelas a la arista) de modo que las fuerzas se cancelen 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 hacer que las fuerzas se cancelen allí también. De esta manera, las incrustaciones de Tutte se pueden utilizar para encontrar diagramas de Schlegel de cada poliedro convexo . Para cada grafo plano 3-conexo G , ya sea 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]

Aplicaciones en el procesamiento de geometría

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

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

donde representa el conjunto de aristas de la superficie 3D original. Cuando los pesos 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 colapsa trivialmente en un único punto en el espacio parametrizado. $E({\mathcal {S}})$ $w_{ij}$

Por lo tanto, se deben proporcionar condiciones de contorno en las que un conjunto de vértices conocidos de la superficie 3D se asignen a puntos conocidos en el espacio parametrizado 2D. Una forma común de elegir dichas 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 que se asignen al anillo exterior de un disco unitario en el espacio parametrizado 2D. Tenga en cuenta que si la superficie 3D es una variedad, los bordes de contorno se pueden detectar verificando que pertenecen solo a una cara de la malla.

Las aplicaciones de la parametrización en gráficos y animación incluyen el mapeo de texturas, entre muchas otras.

Generalizaciones

Colin de Verdière (1991) generalizó el teorema del resorte de Tutte a gráficos en superficies de género superior con curvatura no positiva , donde los bordes están representados por geodésicas ; ^[3] este resultado fue redescubierto posteriormente de forma independiente por Hass y Scott (2015). ^{[4] Delgado-Friedrichs (2005),}^[5] Gortler, Gotsman y Thurston (2006), ^[6] y Lovász (2019) demostraron de forma independiente resultados análogos para gráficos incrustados en un toro . ^[7]

Chilakamarri, Dean y Littman (1995) investigan incrustaciones de grafos tridimensionales de los grafos de politopos de cuatro dimensiones , formados por el mismo método que la incrustación de Tutte: elegir una faceta del politopo como la cara exterior de una incrustación tridimensional y fijar sus vértices en su lugar como los vértices de un poliedro tridimensional en el espacio. Deje que cada vértice restante del politopo sea libre de moverse en el espacio y reemplace cada borde del politopo por un resorte. Luego, encuentre 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. ^[8]

Resultados relacionados

El resultado de que cada grafo plano simple puede dibujarse con aristas de línea recta se llama teorema de Fáry . ^[9] El teorema del resorte de Tutte prueba esto para grafos planos 3-conexos, pero el resultado es cierto de manera más general para grafos planos independientemente de la conectividad. El uso del sistema de resorte de Tutte para un grafo que no es 3-conexo puede dar como resultado 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 la incrustación de Tutte agregando aristas adicionales para hacerlo 3-conexo, dibujando el grafo 3-conexo resultante y luego eliminando las aristas adicionales.

Un grafo es k -vértice-conexo , pero no necesariamente plano, 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 símplex 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 plana de Tutte. ^[10]

En la generación de mallas de elementos finitos , el suavizado laplaciano es un método común para posprocesar una malla generada para mejorar la calidad de sus elementos; ^[11] es particularmente popular para mallas cuadriláteras , para las cuales otros métodos como el algoritmo de Lloyd para suavizado de mallas triangulares 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 para una pequeña cantidad de iteraciones, para evitar grandes distorsiones de tamaños de 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 complicados que combinan fuerzas de atracción sobre los bordes del grafo (como en la incrustación de Tutte) con fuerzas de repulsión entre pares arbitrarios de vértices. Estas fuerzas adicionales pueden hacer que el sistema tenga muchas configuraciones localmente estables en lugar de, como en la incrustación de Tutte, una única solución global. ^[12]

Referencias

^ Tutte, WT (1963), "Cómo dibujar un gráfico", Actas de la London Mathematical Society , 13 : 743–767, doi :10.1112/plms/s3-13.1.743, MR 0158387.
^ ab Rote, Günter (2012), "Realizing planar graphs as convex polytopes", Dibujo de grafos: 19.° simposio internacional, GD 2011, Eindhoven, Países Bajos, 21-23 de septiembre de 2011, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 7034, Springer, págs. 238-241, doi : 10.1007/978-3-642-25878-7_23.
^ Colin de Verdière, Yves. (1991), "Comentario rendre géodésique une triangulación de una superficie?", L'Enseignement Mathématique , 37 (3–4): 201–212, doi :10.5169/seals-58738, MR 1151746.
^ Hass, Joel; Scott, Peter (2015), "Energía simplicial y mapas armónicos simpliciales", Asian Journal of Mathematics , 19 (4): 593–636, arXiv : 1206.2574 , doi : 10.4310/AJM.2015.v19.n4.a2 , MR 3423736, S2CID 15606779.
^ Delgado-Friedrichs, Olaf (2005), "Ubicación de equilibrio de gráficos periódicos y convexidad de teselas planas", Geometría discreta y computacional , 33 (1): 67–81, doi : 10.1007/s00454-004-1147-x , MR 2105751
^ Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Formas unidimensionales discretas en mallas y aplicaciones a la parametrización de mallas 3D", Computer Aided Geometric Design , 23 (2): 83–112, doi :10.1016/j.cagd.2005.05.002, MR 2189438, S2CID 135438.
^ Lovász, Lázsló (2019), Gráficos y geometría (PDF) , Sociedad Estadounidense de Matemáticas, p. 98, ISBN 978-1-4704-5087-8, consultado el 18 de julio de 2019
^ Chilakamarri, Kiran; Dean, Nathaniel; Littman, Michael (1995), "Incorporación tridimensional de Tutte", Actas de la 26.ª Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1995), Congressus Numerantium , 107 : 129–140, MR 1369261.
^ Para la relación entre el teorema de Tutte y el teorema de Fáry, y la historia del redescubrimiento del teorema de Fáry, véase Felsner, Stefan (2012), Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Advanced Lectures in Mathematics, Springer, p. 37, ISBN 978-0-852-2-372-0. 9783322803030.
^ Linial, N. ; Lovász, L. ; Wigderson, A. (1988), "Bandas elásticas, incrustaciones convexas y conectividad de grafos", Combinatorica , 8 (1): 91–102, doi :10.1007/BF02122557, MR 0951998, S2CID 6164458.
^ Herrmann, Leonard R. (1976), "Esquema de generación de cuadrícula laplaciana-isoparamétrica", Journal of the Engineering Mechanics Division , 102 (5): 749–907, doi :10.1061/JMCEA3.0002158.
^ Kobourov, Stephen G. (2012), Incrustadores de resortes y algoritmos de dibujo de gráficos dirigidos por fuerza , arXiv : 1201.3011 , Bibcode :2012arXiv1201.3011K.