En el dibujo de gráficos y la teoría de grafos geométricos , una incrustación de Tutte o una incrustación baricéntrica de una gráfica plana simple conectada a 3 vértices 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 es 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 solución a un sistema de ecuaciones lineales . Resolver las ecuaciones geométricamente produce una incrustación plana .El teorema del resorte de Tutte , probado por WT Tutte ( 1963 ), establece que esta solución única siempre está libre de cruces y, con más fuerza, que cada cara de la incrustación plana resultante es convexa. [1] Se llama teorema del resorte porque tal incrustación se puede encontrar como la posición de equilibrio para un sistema de resortes que representa los bordes del gráfico.
Ejemplo
Deje que G sea la gráfica de un cubo, y (la selección de una de sus caras de cuadrilátero como la cara exterior) fijar los cuatro vértices de la cara exterior en las cuatro esquinas de un cuadrado de la unidad , los puntos cuyas x y Y coordenadas son las cuatro combinaciones de cero y uno. Entonces, si los cuatro vértices restantes se colocan en los cuatro puntos cuyas x y Y coordenadas son combinaciones de 1/3 y 2/3, como en la figura, el resultado será una Tutte incrustación. 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 av , menores en 1/3 y mayores en 1/3; el promedio de estos valores es el mismo que el valor de las 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 gráfico con n vértices, h de los cuales están fijos en su 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 mostró Tutte (1963) , para gráficos planos conectados a tres vértices, este sistema no es degenerado. Por lo tanto, tiene una solución única y (con la cara exterior fija) el gráfico tiene una incrustación de Tutte única. Esta incrustación se puede encontrar en el tiempo polinómico resolviendo el sistema de ecuaciones, por ejemplo, utilizando la eliminación gaussiana . [2]
Representación poliédrica
Según el teorema de Steinitz , las gráficas planas de tres conexiones a las que se aplica el teorema del resorte de Tutte coinciden con las gráficas poliédricas , las gráficas formadas por los vértices y aristas de un poliedro convexo . De acuerdo con la correspondencia de Maxwell-Cremona , una incrustación bidimensional de un gráfico plano 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 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 una incrustación de Tutte, asignar a cada borde una fuerza de atracción 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 bordes para hacer que las fuerzas también se cancelen allí. De esta manera, las incrustaciones de Tutte se pueden utilizar para encontrar diagramas de Schlegel de cada poliedro convexo . Para cada grafo plano G de 3 conexiones , G en sí 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 gráfico 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ías
En el procesamiento de geometría, la incrustación de Tutte se utiliza para la parametrización uv 2Dde superficies 3D más comúnmente para los casos donde la topología de la superficie sigue siendo la misma en todo 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 a través de 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.
dónde representa el conjunto de aristas de la superficie 3D original. Cuando los pesosson positivos (como es el caso anterior), se garantiza que el mapeo es biyectivo sin inversiones. Pero cuando no se aplican más restricciones, la solución que minimiza la energía de distorsión se colapsa trivialmente en un solo 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 mapean a puntos conocidos en el espacio parametrizado 2D. Una forma común de elegir tales condiciones de límite es considerar los vértices en el bucle de límite más grande de la superficie 3D original que luego se puede restringir para ser mapeado en el 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 los límites se pueden detectar verificando que pertenecen a una sola 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éneros superiores con curvatura no positiva , donde los bordes están representados por geodésicas ; [3] Este resultado fue redescubierto más tarde de forma independiente por Hass y Scott (2015) . [4] Los resultados análogos para los gráficos incrustados en un toro fueron demostrados de forma independiente por Delgado-Friedrichs (2005) , [5] por Gortler, Gotsman & Thurston (2006) , [6] y por Lovász (2019) . [7]
Chilakamarri, Dean & Littman (1995) investigan incrustaciones gráficas tridimensionales de las gráficas de politopos de cuatro dimensiones , formadas por el mismo método que la incrustación de Tutte: elija una faceta del politopo como la cara exterior de una incrustación tridimensional, y fija 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 se mueva libremente 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 gráfico plano simple se puede dibujar con bordes en línea recta se llama teorema de Fáry . [9] El teorema del resorte de Tutte demuestra esto para gráficas planas de 3 conexiones, pero el resultado es cierto en general para gráficas planas independientemente de la conectividad. El uso del sistema de resorte de Tutte para un gráfico que no está conectado en 3 puede resultar en degeneraciones, en las que los subgráficos del gráfico dado colapsan en un punto o un segmento de línea; sin embargo, se puede dibujar un gráfico plano arbitrario usando la incrustación de Tutte agregando bordes adicionales para que esté conectado en 3, dibujando el gráfico resultante en 3 conexiones y luego eliminando los bordes adicionales.
Una gráfica está conectada con k -vértices , pero no necesariamente plana, 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 , el casco convexo 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 coloque cada vértice en el promedio de sus vecinos, al igual que 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 de posprocesamiento de 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 malla triangular son menos aplicables. En este método, cada vértice se mueve hacia o hacia el promedio de las posiciones de sus vecinos, pero este movimiento solo se realiza para un pequeño número de iteraciones, para evitar grandes distorsiones de tamaños de elementos o (en el caso de dominios de malla no convexa ) mallas no planas enredadas.
Los sistemas de dibujo de gráficos dirigidos por la fuerza siguen siendo un método popular para visualizar gráficos, pero estos sistemas suelen utilizar sistemas de fuerzas más complicados que combinan fuerzas de atracción en los bordes de los gráficos (como en la incrustación de Tutte) con fuerzas repulsivas 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.
- ^ a b Rote, Günter (2012), "Realizing planar graphs as convex polytopes", Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, 21-23 de septiembre de 2011, Revised Selected Papers , Lecture Notes in Computer Science, 7034 , Springer, págs. 238–241, doi : 10.1007 / 978-3-642-25878-7_23.
- ^ Colin de Verdière, Yves. (1991), "Comment rendre géodésique une triangulation d'une surface?", L'Enseignement Mathématique , 37 (3–4): 201–212, doi : 10.5169 / seals-58738 , MR 1151746.
- ^ Hass, Joel; Scott, Peter (2015), "Simplicial energy and simplicial armic maps", Asian Journal of Mathematics , 19 (4): 593–636, doi : 10.4310 / AJM.2015.v19.n4.a2 , MR 3423736.
- ^ Delgado-Friedrichs, Olaf (2005), "Colocación de equilibrio de gráficas periódicas y convexidad de teselaciones 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), "Discrete one-form on mallas y aplicaciones a la parametrización de malla 3D", Diseño geométrico asistido por computadora , 23 (2): 83–112, doi : 10.1016 / j.cagd.2005.05.002 , MR 2189438.
- ^ Lovász, Lázsló (2019), Gráficos y geometría (PDF) , American Mathematics Society, p. 98, ISBN 978-1-4704-5087-8, consultado el 18 de julio de 2019
- ^ Chilakamarri, Kiran; Dean, Nathaniel; Littman, Michael (1995), "Tridimensional Tutte embedding", Actas de la 26a Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Boca Raton, FL, 1995), Congressus Numerantium , 107 : 129-140, MR 1369261.
- ^ Para la relación entre el teorema de Tutte y Fáry, y la historia del redescubrimiento del teorema de Fáry, ver Felsner, Stefan (2012), Arreglos y gráficos geométricos: algunos capítulos de geometría combinatoria , Conferencias avanzadas de matemáticas, Springer, p. 37, ISBN 9783322803030.
- ^ Linial, N .; Lovász, L .; Wigderson, A. (1988), "Gomas elásticas, incrustaciones convexas y conectividad gráfica", Combinatorica , 8 (1): 91–102, doi : 10.1007 / BF02122557 , MR 0951998.
- ^ Herrmann, Leonard R. (1976), "Esquema de generación de red laplaciano-isoparamétrico", Revista de la División de Ingeniería Mecánica , 102 (5): 749–907.
- ^ Kobourov, Stephen G. (2012), Spring Embedders and Force-Directed Graph Drawing Algorithms , arXiv : 1201.3011 , Bibcode : 2012arXiv1201.3011K.