En el campo matemático de la teoría de grafos , el teorema de Fáry establece que cualquier grafo simple y plano puede dibujarse sin cruces de modo que sus aristas sean segmentos de línea recta . Es decir, la capacidad de dibujar las aristas de los grafos como curvas en lugar de como segmentos de línea recta no permite dibujar una clase más amplia de grafos. El teorema lleva el nombre de István Fáry , aunque fue demostrado de forma independiente por Klaus Wagner (1936), Fáry (1948) y Sherman K. Stein (1951).
Una forma de demostrar el teorema de Fáry es usar la inducción matemática . [1] Sea G un grafo plano simple con n vértices; podemos 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 podríamos agregar una arista en cualquier cara con más lados mientras preservamos la planaridad, contradiciendo el supuesto de planaridad máxima. Elijamos unos tres vértices a , b , c que formen una cara triangular de G . Demostramos por inducción en n que existe una reincrustación combinatoriamente isomorfa en línea recta de G en la que el triángulo abc es la cara exterior de la incrustación. ( Combinatoriamente isomorfo significa que los vértices, aristas y caras del nuevo dibujo se pueden hacer corresponder con los del dibujo anterior, de modo que se conservan todas las incidencias entre aristas, vértices y caras (no solo entre vértices y aristas). Como caso base, el resultado es trivial cuando n = 3 y a , b y c son los únicos vértices en G . Por lo tanto, podemos suponer que n ≥ 4.
Por la fórmula de Euler para grafos planares, G tiene 3 n − 6 aristas; equivalentemente, si uno define la deficiencia de un vértice v en G como 6 − deg ( v ) , la suma de las deficiencias es 12 . Como 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 al menos grado 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, podemos elegir un vértice v con como máximo cinco vecinos que sea diferente de a , b y c . Sea G' formado eliminando v de G y retriangulando la cara f formada eliminando v . Por inducción, G' tiene una reincrustación de línea recta combinatoriamente isomorfa en la que abc es la cara exterior. Como 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 hasta una reincrustación combinatoriamente isomorfa de G en línea recta , v debe colocarse en el polígono y unirse mediante líneas rectas a los vértices del polígono. Por el teorema de la galería de arte , existe un punto interior a P en el que v puede colocarse de modo 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 a la derecha.
De Fraysseix, Pach y Pollack demostraron cómo encontrar en tiempo lineal un dibujo de línea recta en una cuadrícula con dimensiones lineales en el tamaño del gráfico, lo que da 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 la planaridad basada en el orden parcial de incidencia. Su trabajo destacó la existencia de una partición particular de los bordes de un gráfico planar maximalista en tres árboles conocidos como bosque de Schnyder .
El teorema de resortes de Tutte establece que todo grafo plano triconexo puede dibujarse 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). Se llama así porque dicha incrustación puede encontrarse como la posición de equilibrio para un sistema de resortes que representan las aristas del grafo.
El teorema de Steinitz establece que todo grafo plano triconexo puede representarse como las aristas de un poliedro convexo en el espacio tridimensional. Una incrustación en línea recta del tipo descrito por el teorema de Tutte puede formarse proyectando dicha representación poliédrica sobre el plano.
El teorema de empaquetamiento de círculos establece que todo grafo plano puede representarse como el grafo de intersección de una colección de círculos que no se cruzan en el plano. Si se coloca cada vértice del grafo en el centro del círculo correspondiente, se obtiene una representación de línea recta.
Heiko Harborth planteó la cuestión de si todo grafo plano tiene una representación en línea recta en la que todas las longitudes de las aristas sean números enteros. [2] La verdad de la conjetura de Harborth sigue siendo desconocida. Se sabe que existen incrustaciones en línea recta con distancias enteras para grafos cúbicos . [3]
Sachs (1983) planteó la cuestión de si todo gráfico con una incrustación sin enlaces en el espacio euclidiano 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.
