En teoría de grafos, un grafo plano exterior es un grafo que admite un diagrama plano en el que todos los vértices pertenecen a la cara exterior.
Los grafos planos exteriores se pueden caracterizar (de manera similar al teorema de Wagner para grafos planos) por dos menores prohibidos K 4 y K 2,3 , o sus invariantes de Colin de Verdière . Estos gráficos tienen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma un solo ciclo hamiltoniano. Cualquier gráfico de planos exteriores es de 3 colores y tiene una degeneración y un ancho de árbol de 2 como máximo.
Los gráficos outerplanar son un subconjunto de gráficos planos , subgráficos de gráficos paralelos en serie y gráficos circulares . Un gráfico de planar exterior máximo es un gráfico al que no se le puede agregar un borde sin perder la planaridad exterior. También son grafos cordales y de visibilidad .
Chartrand y Harari [1] estudiaron y nombraron gráficos exteriores por primera vez al considerar el problema de determinar la planaridad de los gráficos formados mediante coincidencias perfectas que conectan dos copias del gráfico base (por ejemplo, muchos de los gráficos de Petersen generalizados se forman de esta manera de dos copias del gráfico de ciclo ). Como demostraron, si el grafo base está biconectado , el grafo obtenido de él de la manera descrita es plano si y solo si el grafo base es plano exterior y el emparejamiento forma permutaciones diédricas del ciclo exterior.
Un gráfico plano externo es un gráfico no dirigido que se puede dibujar en un plano sin intersecciones de modo que todos los vértices pertenezcan a la cara exterior ilimitada del dibujo. Es decir, ninguno de los vértices está completamente rodeado de aristas. Alternativamente, un gráfico G es plano exterior si el gráfico formado a partir de G al agregar un nuevo vértice conectado por aristas a todos los demás vértices es plano [2] .
Un gráfico de plano exterior máximo es un gráfico de plano exterior al que no se le puede agregar ningún borde sin violar la propiedad de plano exterior. Cualquier gráfico de plano exterior máximo con n vértices tiene exactamente 2n − 3 aristas, y cualquier cara acotada de un gráfico de plano exterior máximo es un triángulo.
Los gráficos exteriores tienen una caracterización por gráficos prohibidos similar al teorema de Pontryagin-Kuratovsky y al teorema de Wagner para gráficos planos: un gráfico es exterior si y solo si no contiene una subdivisión de un gráfico completo K 4 o un gráfico bipartito completo K 2, 3 [3] . Alternativamente, un grafo es plano exterior si y solo si no contiene K 4 o K 2,3 como menor , el grafo obtenido quitando y contrayendo aristas [4] .
Un grafo sin triángulos es plano exterior si y solo si no contiene subdivisiones K 2,3 [5] .
Un grafo es plano exterior si y solo si su invariante de Colin de Verdière no excede de dos. Los grafos caracterizados de esta manera por el valor del invariante de Colin de Verdière (que no exceda el valor de 1, 3 o 4) son bosques lineales, grafos planos y grafos empotrables sin enlace .
Un gráfico plano exterior es doblemente conexo si y solo si la cara exterior forma un ciclo simple sin vértices repetidos. Un grafo planar exterior es hamiltoniano si y solo si es biconexo. En este caso, la cara exterior forma un único ciclo hamiltoniano [1] [5] . De manera más general, el tamaño del ciclo más largo en un gráfico plano externo es igual al número de vértices en el componente biconectado más largo . Por esta razón, encontrar ciclos hamiltonianos y ciclos más largos en grafos planos exteriores se puede hacer en tiempo lineal , en contraste con la completitud NP de estos problemas para grafos arbitrarios.
Cualquier gráfico plano exterior máximo satisface una condición más fuerte que ser hamiltoniano: es pancíclico de vértice , lo que significa que para cualquier vértice v y cualquier número k entre tres y el número de vértices en el gráfico, hay un ciclo de longitud k que contiene v . Se puede encontrar un ciclo de esta longitud quitando sucesivamente un triángulo conectado al resto del gráfico por una sola arista, de manera que el vértice a quitar no coincida con v , hasta que la cara exterior del gráfico restante sea de longitud k [6] .
Un gráfico plano es plano exterior si y solo si todos sus componentes doblemente conectados son planos exteriores [5] .
Todos los gráficos planos exteriores sin bucles se pueden colorear con solo tres colores [7] . Este hecho aparece de forma destacada en una demostración simplificada del teorema de la galería de arte de Chvatala Fiscom [ 8] . Una coloración con tres colores se puede encontrar en tiempo lineal mediante un algoritmo de coloración codicioso que elimina cualquier vértice con grado como máximo dos y colorea el gráfico restante de forma recursiva, y luego devuelve cada uno de los vértices eliminados con un color diferente de los colores de sus dos vecinos
De acuerdo con el teorema de Vizing , el índice cromático de cualquier gráfico (el número mínimo de colores necesarios para colorear los bordes del gráfico para que no haya dos bordes adyacentes que tengan el mismo color) es igual al grado máximo de los vértices del gráfico, o uno más del grado máximo. Para gráficos planos exteriores, el índice cromático es igual a la potencia máxima, a menos que el gráfico sea un ciclo de longitud impar [9] . Se puede encontrar una coloración de borde con el número óptimo de colores en tiempo lineal basado en una búsqueda en anchura de un árbol dual débil [7] .
Los gráficos exteriores tienen una degeneración máxima de 2: cualquier subgráfico de un gráfico exterior contiene un vértice con un grado máximo de 2 [10] .
Los gráficos de planos exteriores tienen un ancho de árbol máximo de 2, lo que implica que muchos problemas de optimización en gráficos que son NP-completos para gráficos generales pueden resolverse en tiempo polinomial usando programación dinámica si la entrada es un gráfico de planos exteriores. De manera más general, un gráfico k -outerplanar tiene un ancho de árbol O( k ) [11] .
Cualquier gráfico de planos exteriores se puede representar como un gráfico de intersección de rectángulos con lados paralelos a los ejes, de modo que los gráficos de planos exteriores tengan una dimensión de intervalo [12] [13] de como máximo dos [14] [15] .
Cualquier grafo plano exterior es plano . Cualquier grafo plano exterior es un subgrafo de un grafo paralelo-serie [16] . Sin embargo, no todos los gráficos secuenciales paralelos son planos exteriores. El grafo bipartito completo K 2,3 es plano y paralelo-serie, pero no plano exterior. Por otro lado, el grafo completo K 4 es plano, pero ni secuencial paralelo ni plano exterior. Cualquier bosque y cualquier cactus son exteriores [17] .
El gráfico plano dual débil de un gráfico planar exterior incrustado (un gráfico que tiene un vértice para cada cara delimitada del anidamiento y un borde para las caras delimitadas adyacentes) es un bosque, y el gráfico plano dual débil del gráfico de Halin es un gráfico plano exterior. . Un grafo plano es plano exterior si y solo si su dual débil es un bosque, y el grafo es un grafo de Halin si y solo si su dual débil es doblemente conexo y plano exterior [18] .
Existe un concepto del grado de planaridad externa. Una incrustación en un plano exterior de un gráfico es lo mismo que una incrustación en un plano exterior. Para k > 1, se dice que una incrustación plana es k -outerplanar si eliminar un vértice de la cara exterior da como resultado una incrustación ( k − 1)-outerplanar. Un grafo es k -outerplanar si y solo si tiene un k -outerplanar incrustación [19] [5] .
Cualquier grafo plano exterior máximo es un grafo cordal . Cualquier gráfico de plano exterior máximo es un gráfico de visibilidad de polígono simple [20] . Los gráficos planos exteriores máximos se forman como gráficos de triangulación de polígonos . También son ejemplos de 2 árboles , gráficos de secuencias paralelas y gráficos cordales .
Cualquier gráfico plano exterior es un gráfico circular , el gráfico de intersección del conjunto de cuerdas del círculo [21] [22] .