Hispanopedia Wiki
Articulo de referencia

Grafo planar externo

Un grafo exteriorplanar maximal y su coloración de 3 colores. El grafo completo K 4 es el grafo planar más pequeño que no es planar exterior. En teoría de grafos , un grafo plan...

Hispanopedia WikiContenido en espanolLectura gratuita
Un grafo exteriorplanar maximal y su coloración de 3 colores.
El grafo completo K 4 es el grafo planar más pequeño que no es planar exterior.

En teoría de grafos , un grafo planar exterior es un grafo que tiene un dibujo planar en el que todos los vértices pertenecen a la cara exterior del dibujo.

Los grafos exteriores planares se pueden caracterizar (de forma análoga al teorema de Wagner para grafos planares) mediante los dos menores prohibidos K₄ y K₂ , ₃ , o mediante sus invariantes de grafos de Colin de Verdière . Tienen ciclos hamiltonianos si y solo si son biconexos, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Todo grafo exterior planar es 3-coloreable y tiene una degeneración y un ancho de árbol como máximo  de 2.

Los grafos exteriores planares son un subconjunto de los grafos planares , los subgrafos de los grafos serie-paralelo y los grafos circulares . Los grafos exteriores planares máximos , aquellos a los que no se pueden añadir más aristas sin perder su exteriorplanaridad, son también grafos cordales y grafos de visibilidad .

Historia

Los grafos outerplanares fueron estudiados y nombrados por primera vez por Chartrand y Harary (1967) , en relación con el problema de determinar la planaridad de los grafos formados mediante un emparejamiento perfecto para conectar dos copias de un grafo base (por ejemplo, muchos de los grafos generalizados de Petersen se forman de esta manera a partir de dos copias de un grafo cíclico ). Como demostraron, cuando el grafo base es biconexo , un grafo construido de esta manera es planar si y solo si su grafo base es outerplanar y el emparejamiento forma una permutación diedral de su ciclo exterior. Chartrand y Harary también demostraron un análogo del teorema de Kuratowski para grafos outerplanares, que establece que un grafo es outerplanar si y solo si no contiene una subdivisión de uno de los dos grafos K 4 o K 2,3 .

Definición y caracterizaciones

Un grafo exteriorplanar es un grafo no dirigido que puede dibujarse en el plano sin intersecciones de tal manera que todos sus vértices pertenezcan a la cara no delimitada del dibujo. Es decir, ningún vértice está completamente rodeado por aristas. Alternativamente, un grafo G es exteriorplanar si el grafo formado a partir de G añadiendo un nuevo vértice, con aristas que lo conectan a todos los demás vértices, es un grafo planar . [ 1 ] [ 2 ]

Un grafo exteriorplanar maximal es un grafo exteriorplanar al que no se le pueden añadir aristas adicionales sin perder su planaridad exterior. Todo grafo exteriorplanar maximal con n vértices tiene exactamente 2n − 3 aristas, y toda cara acotada de un grafo exteriorplanar maximal es un triángulo.  

Gráficos prohibidos

Los grafos exteriores planares tienen una caracterización de grafos prohibidos análoga al teorema de Kuratowski y al teorema de Wagner para grafos planares: un grafo es exteriorplanar 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 exteriorplanar 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 libre de triángulos es exteriorplanar si y solo si no contiene una subdivisión de K 2,3 . [ 5 ]

Colin de Verdière invariante

Un grafo es planar exterior si y solo si su invariante de grafo de Colin de Verdière es como máximo dos. Los grafos caracterizados de manera similar por tener como máximo uno, tres o cuatro invariantes de Colin de Verdière son, respectivamente, los bosques lineales, los grafos planares y los grafos incrustables sin enlaces .

Propiedades

Biconectividad y hamiltonicidad

Un grafo planar exterior es biconexo si y solo si la cara exterior del grafo 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 el único ciclo hamiltoniano. [ 6 ] De manera más general, el tamaño del ciclo más largo en un grafo planar exterior es igual al número de vértices en su componente biconexa más grande . Por esta razón, encontrar ciclos hamiltonianos y ciclos más largos en grafos planares exteriores puede resolverse en tiempo lineal , en contraste con la NP-completitud de estos problemas para grafos arbitrarios.

Todo grafo planar exterior maximal 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 del grafo, existe un ciclo de longitud k que contiene a v . Un ciclo de esta longitud se puede encontrar eliminando repetidamente un triángulo conectado al resto del grafo por una sola arista, de manera que el vértice eliminado no sea v , hasta que la cara exterior del grafo restante tenga longitud k . [ 7 ]

Un grafo planar es exteriorplanar si y solo si cada una de sus componentes biconexas es exteriorplanar. [ 5 ]

Colorante

Todos los grafos exteriores planares sin bucles pueden colorearse usando solo tres colores; [ 8 ] este hecho aparece prominentemente en la demostración simplificada del teorema de la galería de arte de Chvátal por Fisk (1978) . Se puede encontrar una coloración de 3 colores en tiempo lineal mediante un algoritmo de coloración voraz que elimina cualquier vértice de grado como máximo dos, colorea el grafo restante recursivamente y luego vuelve a agregar el vértice eliminado con un color diferente a 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 manera que no haya dos aristas adyacentes con el mismo color) es igual al grado máximo de cualquier vértice del grafo o a uno más el grado máximo. Sin embargo, en un grafo exteriorplanar 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 mediante un recorrido en anchura del árbol dual débil. [ 8 ]

Otras propiedades

Los grafos exteriores planares tienen una degeneración de como máximo dos: cada subgrafo de un grafo exterior planar contiene un vértice con grado de como máximo dos. [ 10 ]

Los grafos outerplanares tienen un ancho de árbol como máximo dos, 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 outerplanar. De forma más general, los grafos k -outerplanares tienen un ancho de árbol O( k ). [ 11 ]

Todo grafo planar exterior puede representarse como un grafo de intersección de rectángulos alineados con los ejes en el plano, por lo que los grafos planares exteriores tienen una boxicidad como máximo de dos. [ 12 ]

Un grafo cactus . Los cactus forman una subclase de los grafos exteriores planares.

Todo grafo exteriorplanar es un grafo planar . Todo grafo exteriorplanar es también un subgrafo de un grafo serie-paralelo . [ 13 ] Sin embargo, no todos los grafos serie-paralelo planares son exterioresplanares. El grafo bipartito completo K 2,3 es planar y serie-paralelo, pero no exteriorplanar. Por otro lado, el grafo completo K 4 es planar, pero no es ni serie-paralelo ni exteriorplanar. Todo grafo bosque y todo grafo cactus son exterioresplanares. [ 14 ]

El grafo dual planar débil de un grafo exteriorplanar incrustado (el grafo que tiene un vértice por cada cara acotada de la incrustación y una arista por cada par de caras acotadas adyacentes) es un bosque, y el dual planar débil de un grafo de Halin es un grafo exteriorplanar. Un grafo planar es exteriorplanar si y solo si su dual débil es un bosque, y es de Halin si y solo si su dual débil es biconexo y exteriorplanar. [ 15 ]

Existe una noción de grado de planaridad externa. Una incrustación 1-externa de un grafo es lo mismo que una incrustación externa. Para k > 1, se dice que una incrustación planar es k -externa si al eliminar los vértices de la cara externa se obtiene una incrustación ( k − 1)-externa. Un grafo es k -externa si tiene una incrustación k -externa. [ 16 ]    

Un grafo exterior 1-planar , de forma análoga a los grafos 1-planares, se puede dibujar en un disco, con los vértices en el borde del disco y con como máximo un cruce por arista.

Todo grafo exteriorplanar maximal es un grafo cordal . Todo grafo exteriorplanar maximal es el grafo de visibilidad de un polígono simple . [ 17 ] Los grafos exterioresplanares maximales también se forman como los grafos de triangulaciones de polígonos . Son ejemplos de 2-árboles , de grafos serie-paralelo 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 ]

Notas

Referencias

  • Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en grafos planares", Journal of the ACM , 41 (1): 153–180 , doi : 10.1145/174644.174650 , S2CID 9706753 .
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "El problema de las incrustaciones exteriores en pseudosuperficies", Ars Combinatoria , 71 : 79– 91.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "Conjuntos de obstrucción para gráficos de superficie exterior de plátanos", Ars Combinatoria , 73 : 65– 77.
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2006), "Grafos no numerables con todos sus vértices en una cara", Acta Mathematica Hungarica , 112 (4): 307–313 , doi : 10.1007/s10474-006-0082-0 , hdl : 11441/163886 , S2CID 123241658 .
  • Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2010), "Incrustabilidad externa en ciertas pseudosuperficies que surgen de tres esferas", Matemáticas Discretas , 310 (23): 3359– 3367, doi : 10.1016/j.disc.2010.07.027.
  • Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics , ISBN 0-89871-432-X.
  • Chartrand, Gary ; Harary, Frank (1967), "Gráficos de permutación plana" , Annales de l'Institut Henri Poincaré B , 3 (4): 433– 438, SEÑOR 0227041 .
  • Diestel, Reinhard (2000), Teoría de grafos , Textos de posgrado en matemáticas , vol.  173, Springer-Verlag, pág.  107, ISBN 0-387-98976-5.
  • El-Gindy, H. (1985), Descomposición jerárquica de polígonos con aplicaciones , tesis doctoral, Universidad McGill. Citado por Brandstädt, Le y Spinrad (1999) .
  • Felsner, Stefan (2004), Gráficos y arreglos geométricos: algunos capítulos de geometría combinatoria , Vieweg+Teubner Verlag, pág.  6, ISBN 978-3-528-06972-8.
  • Fiorini, Stanley (1975), "Sobre el índice cromático de grafos exteriores planares", Journal of Combinatorial Theory , Serie B, 18 (1): 35–38 , doi : 10.1016/0095-8956(75)90060-X.
  • Fisk, Steve (1978), "Una breve demostración del teorema del vigilante de Chvátal", Journal of Combinatorial Theory , Serie B, 24 (3): 374, doi : 10.1016/0095-8956(78)90059-X.
  • Fleischner, Herbert J.; Geller, DP; Harary, Frank (1974), "Grafos fuera del plano y duales débiles", Journal of the Indian Mathematical Society , 38 : 215–219 , MR 0389672 .
  • Kane, Vinay G.; Basu, Sanat K. (1976), "Sobre la profundidad de un grafo planar", Matemáticas Discretas , 14 (1): 63– 67, doi : 10.1016/0012-365X(76)90006-6.
  • Li, Ming-Chu; Corneil, Derek G .; Mendelsohn, Eric (2000), "Panciclicidad y NP-completitud en grafos planares", Discrete Applied Mathematics , 98 (3): 219– 225, doi : 10.1016/S0166-218X(99)00163-8.
  • Lick, Don R.; White, Arthur T. (1970), " k -grafos degenerados", Canadian Journal of Mathematics , 22 (5): 1082– 1096, doi : 10.4153/CJM-1970-125-1 , S2CID 124609794 .
  • Lin, Yaw-Ling; Skiena, Steven S. (1995), "Aspectos de complejidad de los grafos de visibilidad", International Journal of Computational Geometry and Applications , 5 (3): 289– 312, doi : 10.1142/S0218195995000179.
  • Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Coloración eficiente de vértices y aristas de grafos exteriores planares", SIAM Journal on Algebraic and Discrete Methods , 7 : 131–136 , doi : 10.1137/0607016.
  • Scheinerman, ER (1984), Clases de intersección y parámetros de intersección múltiple de un grafo , tesis doctoral, Universidad de Princeton. Citado por Brandstädt, Le y Spinrad (1999) .
  • Sysło, Maciej M. (1979), "Caracterizaciones de grafos exteriores planares", Matemáticas Discretas , 26 (1): 47– 53, doi : 10.1016/0012-365X(79)90060-8.
  • Sysło, Maciej M.; Proskurowski, Andrzej (1983), "Sobre los grafos de Halin", Teoría de grafos: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics , vol  . 1018, Springer-Verlag, pp. 248–256 , doi : 10.1007/BFb0071635 , ISBN  978-3-540-12687-4.
  • Unger, Walter (1988), "Sobre la k -coloración de grafos circulares", Actas del 5.º Simposio sobre Aspectos Teóricos de la Informática (STACS '88) , Lecture Notes in Computer Science , vol.  294, Springer-Verlag, pp. 61–72 , doi : 10.1007/BFb0035832 , ISBN  3-540-18834-7.
  • Wessel, W.; Pöschel, R. (1985), "Sobre grafos circulares", en Sachs, Horst (ed.), Grafos, hipergrafos y aplicaciones: Actas de la Conferencia sobre Teoría de Grafos celebrada en Eyba, del 1 al 5 de octubre de 1984 , Teubner-Texte zur Mathematik, vol.  73, BG Teubner, pp . 207–210 . Citado por Unger (1988) .
  • Wiegers, Manfred (1986), "Reconocimiento de grafos fuera del plano en tiempo lineal", Conceptos de teoría de grafos en informática , Lecture Notes in Computer Science , vol.  246, pp. 165–176 , doi : 10.1007/3-540-17218-1_57 , ISBN  978-3-540-17218-5.
  • Grafos fuera del plano en el Sistema de Información sobre Clases de Grafos y sus Inclusiones.
  • Weisstein, Eric W. "Grafo fuera del plano" . MathWorld .