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