En teoría de grafos , un grafo exterior-planar es un grafo que tiene un dibujo plano en el que todos los vértices pertenecen a la cara exterior del dibujo.
Los grafos extraplanares pueden caracterizarse (de manera análoga al teorema de Wagner para grafos planares) por los dos menores prohibidos K 4 y K 2,3 , o por sus invariantes de grafo de Colin de Verdière . Tienen ciclos hamiltonianos si y solo si son biconexos, en cuyo caso la cara externa forma el único ciclo hamiltoniano. Cada grafo extraplanar es 3-coloreable y tiene degeneración y ancho de árbol como máximo 2.
Los grafos exteriores-planares son un subconjunto de los grafos planares , los subgrafos de grafos en serie-paralelos y los grafos circulares . Los grafos exteriores-planares máximos , aquellos a los que no se les pueden añadir más aristas mientras se conserva la exterior-planaridad, también son grafos cordales y grafos de visibilidad .
Los grafos exteriormente planos fueron estudiados y nombrados por primera vez por Chartrand y Harary (1967), en conexión con el problema de determinar la planaridad de los grafos formados mediante el uso de un emparejamiento perfecto para conectar dos copias de un grafo base (por ejemplo, muchos de los grafos de Petersen generalizados se forman de esta manera a partir de dos copias de un grafo de ciclo ). Como mostraron, cuando el grafo base es biconexo , un grafo construido de esta manera es planar si y solo si su grafo base es exteriormente plano y el emparejamiento forma una permutación diedral de su ciclo externo. Chartrand y Harary también demostraron un análogo del teorema de Kuratowski para grafos exteriormente planos, que un grafo es exteriormente plano si y solo si no contiene una subdivisión de uno de los dos grafos K 4 o K 2,3 .
Un grafo exterior-planar es un grafo no dirigido que se puede dibujar en el plano sin cruces de tal manera que todos los vértices pertenecen a la cara no acotada del dibujo. Es decir, ningún vértice está totalmente rodeado por aristas. Alternativamente, un grafo G es exterior-planar si el grafo formado a partir de G añadiendo un nuevo vértice, con aristas que lo conectan con todos los demás vértices, es un grafo plano . [1] [2]
Un grafo maximal exterior-planar es un grafo maximal exterior-planar al que no se le pueden añadir aristas adicionales, pero que conserva la exterior-planaridad. Todo grafo maximal exterior-planar con n vértices tiene exactamente 2 n − 3 aristas, y cada cara acotada de un grafo maximal exterior-planar es un triángulo.
Los grafos exteriormente planos tienen una caracterización de grafo prohibido análoga al teorema de Kuratowski y al teorema de Wagner para grafos planares: un grafo es exteriormente plano si y solo si no contiene una subdivisión del grafo completo K 4 o del grafo bipartito completo K 2,3 . [3] Alternativamente, un grafo es exteriormente plano si y solo si no contiene K 4 o K 2,3 como un menor , un grafo obtenido a partir de él eliminando y contrayendo aristas. [4]
Un grafo sin triángulos es exteriormente plano si y sólo si no contiene una subdivisión de K 2,3 . [5]
Un grafo es exteriormente planar si y solo si su invariante de grafo de Colin de Verdière es como máximo dos. Los grafos que se caracterizan de manera similar por tener un invariante de Colin de Verdière como máximo uno, tres o cuatro son respectivamente los bosques lineales, los grafos planares y los grafos integrables sin enlaces .
Un grafo exterior-planar es biconexo si y solo si la cara exterior del grafo forma un ciclo simple sin vértices repetidos. Un grafo exterior-planar es hamiltoniano si y solo si es biconexo; en este caso, la cara exterior forma el único ciclo hamiltoniano. [6] De manera más general, el tamaño del ciclo más largo en un grafo exterior-planar es el mismo que el número de vértices en su componente biconexo más grande . Por esta razón, encontrar ciclos hamiltonianos y ciclos más largos en grafos exteriores-planares se puede resolver en tiempo lineal , en contraste con la NP-completitud de estos problemas para grafos arbitrarios.
Todo grafo maximalista exteriorplanar satisface una condición más fuerte que la hamiltonicidad: es pancíclico de nodos , lo que significa que para cada vértice v y cada k en el rango de tres al número de vértices en el grafo, hay un ciclo de longitud k que contiene a v . Un ciclo de esta longitud se puede encontrar eliminando repetidamente un triángulo que esté conectado al resto del grafo por un solo borde, de modo que el vértice eliminado no sea v , hasta que la cara exterior del grafo restante tenga una longitud k . [7]
Un gráfico plano es exteriormente plano si y sólo si cada uno de sus componentes biconectados es exteriormente plano. [5]
Todos los grafos exteriores-planares sin bucles pueden colorearse utilizando solo tres colores; [8] este hecho se destaca de manera destacada en la prueba simplificada del teorema de la galería de arte de Chvátal por Fisk (1978). Se puede encontrar una coloración triple en tiempo lineal mediante un algoritmo de coloración voraz que elimina cualquier vértice de grado dos como máximo, colorea el grafo restante de manera recursiva y luego agrega nuevamente el vértice eliminado con un color diferente de los colores de sus dos vecinos.
Según el teorema de Vizing , el índice cromático de cualquier grafo (el número mínimo de colores necesarios para colorear sus aristas de modo que no haya dos aristas adyacentes del mismo color) es el grado máximo de cualquier vértice del grafo o uno más el grado máximo. Sin embargo, en un grafo exterior plano conexo, el índice cromático es igual al grado máximo excepto cuando el grafo forma un ciclo de longitud impar. [9] Se puede encontrar una coloración de aristas con un número óptimo de colores en tiempo lineal basándose en un recorrido en amplitud del árbol dual débil. [8]
Los grafos extraplanares tienen una degeneración de como máximo dos: cada subgrafo de un grafo extraplanar contiene un vértice con grado como máximo dos. [10]
Los grafos de plano exterior tienen un ancho de árbol de dos como máximo, lo que implica que muchos problemas de optimización de grafos que son NP-completos para grafos arbitrarios pueden resolverse en tiempo polinomial mediante programación dinámica cuando la entrada es de plano exterior. En términos más generales, los grafos k -de plano exterior tienen un ancho de árbol de O( k ). [11]
Cada gráfico exterior-planar se puede representar como un gráfico de intersección de rectángulos alineados con el eje en el plano, por lo que los gráficos exteriores-planares tienen boxicidad como máximo dos. [12]
Todo grafo exterior-planar es un grafo plano . Todo grafo exterior-planar es también un subgrafo de un grafo serie-paralelo . [13] Sin embargo, no todos los grafos serie-paralelos planos son exteriores-planares. El grafo bipartito completo K 2,3 es plano y serie-paralelo, pero no exterior-planar. Por otra parte, el grafo completo K 4 es plano, pero no serie-paralelo ni exterior-planar. Todo grafo de bosque y todo grafo de cactus son exteriores-planares. [14]
El grafo dual débil planar de un grafo exterior planar incrustado (el grafo que tiene un vértice para cada cara acotada de la incrustación y una arista para cada par de caras adyacentes acotadas) es un bosque, y el dual débil planar de un grafo Halin es un grafo exterior planar. Un grafo planar es exterior planar si y solo si su dual débil es un bosque, y es Halin si y solo si su dual débil es biconexo y exterior planar. [15]
Existe una noción de grado de planaridad externa. Una incrustación 1-externamente plana de un grafo es lo mismo que una incrustación externamente plana. Para k > 1, se dice que una incrustación plana es k -externamente plana si la eliminación de los vértices en la cara externa da como resultado una incrustación ( k − 1)-externamente plana. Un grafo es k -externamente plana si tiene una incrustación k -externamente plana. [16]
Un gráfico 1-planar externo , de manera análoga a los gráficos 1-planares , se puede dibujar en un disco, con los vértices en el límite del disco y con como máximo un cruce por borde.
Todo grafo maximal exteriorplanar es un grafo cordal . Todo grafo maximal exteriorplanar es el grafo de visibilidad de un polígono simple . [17] Los grafos maximal exterioresplanares también se forman como grafos de triangulaciones de polígonos . Son ejemplos de 2-árboles , de grafos en serie-paralelos y de grafos cordales .
Todo grafo exterior-planar es un grafo circular , el grafo de intersección de un conjunto de cuerdas de un círculo. [18]