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 , y .

Demostración

Una forma de probar el teorema de Fáry es usar el método de inducción:La prueba que sigue se encuentra en .

Sea un grafo plano simple con vértices; se pueden agregar aristas si es necesario para que sea un grafo máximamente plano. Si < 3, el resultado es trivial. Si ≥ 3, entonces todas las caras de 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 que formen una cara triangular de . Se prueba por inducción sobre que existe una reincrustación combinatoriamente isomorfa de mediante segmentos rectos en la que el triángulo 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 y , y son los únicos vértices en . Así, se puede suponer que ≥ 4.

Por la fórmula de Euler para grafos planos, tiene aristas. De manera equivalente, si se define la deficiencia de un vértice en como , la suma de las deficiencias es . Dado que tiene al menos cuatro vértices y todas las caras de son triángulos, se deduce que cada vértice en tiene un grado de al menos tres. Por lo tanto, cada vértice en 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 con cinco vecinos como máximo que sea diferente de , y . Sea ahora , que se obtiene quitando de y retriangulando la cara formada quitando . Por inducción, tiene una reintegración mediante segmentos rectos combinatoriamente isomórfica en la que es la cara exterior. Debido a que la reincrustación de era combinatoriamente isomorfa a , al quitarle las aristas que se agregaron para crear , queda la cara , que ahora es un polígono con cinco lados como máximo. Para completar el dibujo de un nueva incrustación isomórfica combinatoria mediante segmentos rectos de , 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 en el que se puede colocar de manera que las aristas desde hasta los vértices de 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 mediante 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 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.

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 conjetura de Harborth permanecía sin demostrar . Sin embargo, se sabe que existen incrustaciones mediante segmentos rectos de longitud entera para grafos cúbicos..

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.

Referencias

Bibliografía . . . . . . . . . . . . .

Categoría:Grafos planares Categoría:Teoremas de la teoría de grafos