Teorema de Fáry

En el campo matemático de la teoría de grafos, el teorema de Fáry establece que cualquier grafo plano simple puede ser dibujado sin cruces, de modo que todas sus aristas sean segmentos de recta. Es decir, la posibilidad de dibujar aristas curvas en lugar de segmentos de línea recta no permite dibujar una clase más grande de grafos. El teorema lleva el nombre de István Fáry, aunque fue demostrado de forma independiente por Klaus Wagner (1936),István Fáry (1948) y Sherman K. Stein (1951).

Mediante un homeomorfismo adecuado, B y D también se pueden conectar con un segmento recto

Demostración

Paso de inducción para la demostración del teorema de Fáry

Una forma de probar el teorema de Fáry es usar el método de inducción:​

Sea G un grafo plano simple con n vértices; se pueden agregar aristas si es necesario para que G sea un grafo máximamente plano. Si n < 3, el resultado es trivial. Si n ≥ 3, entonces todas las caras de G deben ser triángulos, ya que se podría agregar una arista a cualquier cara con más lados conservando la planaridad, contradiciendo la suposición de planaridad máxima. Ahora, se eligen tres vértices a, b, c que formen una cara triangular de G. Se prueba por inducción sobre n que existe una reincrustación combinatoriamente isomorfa de G mediante segmentos rectos en la que el triángulo abc es la cara exterior de la incrustación ("combinatoriamente isomórfica" significa que los vértices, aristas y caras del nuevo dibujo se pueden hacer corresponder con los del dibujo anterior, de modo que todas las incidencias entre aristas, vértices y caras, no solo entre vértices y aristas, se conservan). Como caso base, el resultado es trivial cuando n= 3 y a, b y c son los únicos vértices en G. Así, se puede suponer que n ≥ 4.

Por la fórmula de Euler para grafos planos, G tiene 3n − 6 aristas. De manera equivalente, si se define la deficiencia de un vértice v en G como 6 − grado(v), la suma de las deficiencias es 12. Dado que G tiene al menos cuatro vértices y todas las caras de G son triángulos, se deduce que cada vértice en G tiene un grado de al menos tres. Por lo tanto, cada vértice en G tiene deficiencia como máximo tres, por lo que hay al menos cuatro vértices con deficiencia positiva. En particular se puede elegir un vértice v con cinco vecinos como máximo que sea diferente de a, b y c. Sea ahora G', que se obtiene quitando v de G y retriangulando la cara f formada quitando v. Por inducción, G' tiene una reintegración mediante segmentos rectos combinatoriamente isomórfica en la que abc es la cara exterior. Debido a que la reincrustación de G' era combinatoriamente isomorfa a G', al quitarle las aristas que se agregaron para crear G', queda la cara f, que ahora es un polígono P con cinco lados como máximo. Para completar el dibujo de un nueva incrustación isomórfica combinatoria mediante segmentos rectos de G, v debe colocarse en el polígono y unirse mediante líneas rectas a los vértices del polígono. Por teorema de la galería de arte, existe un punto interior a P en el que se puede colocar v de manera que las aristas desde v hasta los vértices de P no crucen ninguna otra arista, completando la prueba.

El paso de inducción de esta prueba se ilustra en la imagen de la derecha.

Resultados relacionados

De Fraysseix, Pach y Pollack demostraron cómo encontrar en tiempo lineal un dibujo de segmentos rectos en una cuadrícula con dimensiones lineales dependientes del tamaño del grafo, dando un conjunto de puntos universal con tamaño cuadrático. Schnyder ha seguido un método similar para demostrar límites mejorados y una caracterización de planaridad basada en el orden parcial de incidencia. Su trabajo enfatizó la existencia de una partición particular de los bordes de un grafo plano máximo en tres árboles, conocido como bosque de Schnyder.

Las propiedades del embebido de Tutte permiten establecer que cada grafo plano 3-conectado se puede dibujar en un plano sin cruces, de modo que sus aristas sean segmentos de línea recta y una cara exterior sea un polígono convexo (Tutte 1963). Dicho embebido se puede determinar nediante la posición de equilibrio de un sistema de resortes que representa las aristas del grafo.

El teorema de Steinitz establece que cada grafo plano 3-conectado se puede representar como los bordes de un poliedro convexo en un espacio tridimensional. Se puede formar un embebido con líneas rectas de $G,$ del tipo descrito por el teorema de Tutte, proyectando dicha representación poliédrica en el plano.

El teorema de empaquetamiento de circunferencias establece que cada grafo plano puede representarse como el grafo de intersección de una colección de círculos que no se cruzan en el plano. Colocar cada vértice del grafo en el centro del círculo correspondiente conduce a una representación mediante líneas rectas.

Problemas no resueltos de la matemática: ¿Todos los gráficos planos tienen una representación mediante segmentos rectilíneos en la que todas las longitudes de las aristas son números enteros??

Heiko Harborth planteó la cuestión de si cada grafo plano tiene una representación mediante segmentos rectos en la que todas las longitudes de las aristas son números enteros.​ La validez de la conjectura de Harborth permanecía sin demostrar a 2014. Sin embargo, se sabe que existen incrustaciones mediante segmentos rectos de longitud entera para grafos cúbicos.​

Sachs (1983) planteó la cuestión de si cada grafo con un embebido sin enlaces en un espacio euclídeo tridimensional tiene una incrustación sin enlaces en la que todos los bordes están representados por segmentos de línea recta, de manera análoga al teorema de Fáry para incrustaciones bidimensionales.

Véase también

• Minimización de recodos

Bibliografía

• Fáry, István (1948), «On straight-line representation of planar graphs», Acta Sci. Math. (Szeged) 11: 229-233, MR 0026311 ..
• de Fraysseix, Hubert; Pach, János; Pollack, Richard (1988), «Small sets supporting Fary embeddings of planar graphs», Twentieth Annual ACM Symposium on Theory of Computing, pp. 426-433, ISBN 0-89791-264-0, S2CID 15230919, doi:10.1145/62212.62254 ..
• de Fraysseix, Hubert; Pach, János; Pollack, Richard (1990), «How to draw a planar graph on a grid», Combinatorica 10: 41-51, MR 1075065, S2CID 6861762, doi:10.1007/BF02122694 ..
• Geelen, Jim; Guo, Anjie; McKinnon, David (2008), «Straight line embeddings of cubic planar graphs with integer edge lengths», J. Graph Theory 58 (3): 270-274, doi:10.1002/jgt.20304 ..
• Harborth, H.; Kemnitz, A.; Moller, M.; Sussenbach, A. (1987), «Ganzzahlige planare Darstellungen der platonischen Korper», Elem. Math. 42: 118-122 ..
• Kemnitz, A.; Harborth, H. (2001), «Plane integral drawings of planar graphs», Discrete Math. 236 (1–3): 191-195, doi:10.1016/S0012-365X(00)00442-8 ..
• Mohar, Bojan (2003), Problems from the book Graphs on Surfaces ..
• Mohar, Bojan; Thomassen, Carsten (2001), Graphs on Surfaces, Johns Hopkins University Press, pp. roblem 2.8.15, ISBN 0-8018-6689-8 ..
• Sachs, Horst (1983), «On a spatial analogue of Kuratowski's theorem on planar graphs — An open problem», en Horowiecki, M.; Kennedy, J. W.; Sysło, M. M., eds., Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics 1018, Springer-Verlag, pp. 230-241, ISBN 978-3-540-12687-4, doi:10.1007/BFb0071633 ..
• Schnyder, Walter (1990), «Embedding planar graphs on the grid», Proc. 1st ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 138-148, ISBN 9780898712513 ..
• Stein, S. K. (1951), «Convex maps», Proceedings of the American Mathematical Society 2 (3): 464-466, JSTOR 2031777, MR 0041425, doi:10.2307/2031777 ..
• Tutte, W. T. (1963), «How to draw a graph», Proceedings of the London Mathematical Society 13: 743-767, MR 0158387, doi:10.1112/plms/s3-13.1.743 ..
• Wagner, Klaus (1936), «Bemerkungen zum Vierfarbenproblem», Jahresbericht der Deutschen Mathematiker-Vereinigung 46: 26-32 ..

• Datos: Q4455031