En teoría de grafos , un grafo plano exterior es un grafo que tiene un dibujo plano en el que todos los vértices pertenecen a la cara exterior del dibujo.
Los gráficos planos exteriores pueden caracterizarse (de forma análoga al teorema de Wagner para gráficos planos) por los dos menores prohibidos K 4 y K 2,3 , o por sus invariantes de gráfico de Colin de Verdière . Tienen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el ciclo hamiltoniano único. Cada gráfico del plano exterior tiene 3 colores y tiene una degeneración y un ancho de árbol como máximo 2.
Las gráficas planas externas son un subconjunto de las gráficas planas , las subgráficas de las gráficas en serie-paralelas y las gráficas circulares . Los gráficos planos externos máximos , aquellos a los que no se pueden agregar más bordes mientras se conserva la planitud externa, también son gráficos cordales y gráficos de visibilidad .
Historia
Chartrand y Harary (1967) estudiaron y nombraron por primera vez las gráficas exteriores en relación con el problema de determinar la planaridad de las gráficas formadas mediante el uso de una correspondencia perfecta para conectar dos copias de una gráfica base (por ejemplo, muchas de las gráficas de Petersen se forman de esta manera a partir de dos copias de un gráfico de ciclo ). Como mostraron, cuando el gráfico base está biconectado , un gráfico construido de esta manera es plano si y solo si su gráfico base es plano exterior y la coincidencia forma una permutación diedro de su ciclo exterior. Chartrand y Harary también demostraron un análogo del teorema de Kuratowski para gráficos planos exteriores, que un gráfico es plano exterior si y solo si no contiene una subdivisión de uno de los dos gráficos K 4 o K 2,3 .
Definición y caracterizaciones
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 pertenecen a la cara ilimitada del dibujo. Es decir, ningún vértice está totalmente rodeado por aristas. Alternativamente, un gráfico G es plano exterior si el gráfico formado a partir de G al agregar un nuevo vértice, con bordes que lo conectan con todos los demás vértices, es un gráfico plano . [1]
Un gráfico de plano exterior máximo es un gráfico de plano exterior al que no se le pueden agregar bordes adicionales mientras se conserva la planificación exterior. Cada grafo plano exterior máximo con n vértices tiene exactamente 2 n - 3 aristas, y cada cara acotada de un grafo plano exterior máximo es un triángulo.
Gráficos prohibidos
Outerplanar gráficos tienen una caracterización gráfico prohibido análogo al teorema de Kuratowski y el teorema de Wagner para grafos planos: un gráfico es outerplanar si y sólo si no contiene una subdivisión de la gráfica completa K 4 o la completa bipartito gráfico K 2,3 . [2] Alternativamente, un gráfico es plano exterior si y solo si no contiene K 4 o K 2,3 como menor , un gráfico obtenido de él eliminando y contrayendo bordes. [3]
Un gráfico sin triángulos es plano exterior si y solo si no contiene una subdivisión de K 2,3 . [4]
Colin de Verdière invariante
Un gráfico es plano exterior si y solo si su invariante de 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 invariante como máximo uno, tres o cuatro son, respectivamente, los bosques lineales, los gráficos planos y los gráficos incrustables sin enlaces .
Propiedades
Biconnectividad y hamiltonicidad
Un gráfico plano exterior está biconectado si y solo si la cara exterior del gráfico forma un ciclo simple sin vértices repetidos. Un gráfico plano exterior es hamiltoniano si y solo si está biconectado; en este caso, la cara exterior forma el ciclo hamiltoniano único. [5] De manera más general, el tamaño del ciclo más largo en un gráfico plano exterior es el mismo que el número de vértices en su componente biconectado más grande . Por esta razón, la búsqueda de ciclos hamiltonianos y ciclos más largos en gráficos planos exteriores se puede resolver en tiempo lineal , en contraste con la NP-completitud de estos problemas para gráficos arbitrarios.
Cada grafo plano exterior 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 vy 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 solo si cada uno de sus componentes biconectados es plano exterior. [4]
Colorante
Todos los gráficos planos exteriores sin bucle se pueden colorear utilizando sólo tres colores; [7] este hecho un lugar destacado en la prueba simplificada de la Chvátal galería de arte teorema por Fisk (1978) . Se puede encontrar una coloración 3 en tiempo lineal mediante un algoritmo de coloración codicioso 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 no haya dos bordes adyacentes con 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 basado en un recorrido en anchura del árbol dual débil. [7]
Otras propiedades
Los gráficos planos exteriores tienen una degeneración como máximo dos: cada subgráfico de un gráfico plano exterior contiene un vértice con un grado como máximo dos. [9]
Los gráficos de planos exteriores tienen un ancho de árbol como máximo 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 planos externos. De manera más general, los gráficos k -outerpillarlanar tienen un ancho de árbol O ( k ). [10]
Cada gráfico del plano exterior 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 del plano exterior tienen una boxicidad como máximo dos. [11]
Familias relacionadas de gráficos
Cada grafo plano exterior es un grafo plano . Cada gráfico del plano exterior es también un subgráfico de un gráfico en serie-paralelo . [12] Sin embargo, no todas las series planas-gráficas paralelas son planas externas. El gráfico bipartito completo K 2,3 es plano y paralelo en serie, pero no plano exterior. Por otro lado, el gráfico completo K 4 es plano, pero no en serie, paralelo ni plano exterior. Cada bosque y cada gráfico de cactus son planos externos. [13]
El gráfico doble plano débil de un gráfico plano exterior 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 doble plano débil de un gráfico de Halin es un gráfico plano exterior. Un gráfico plano es plano exterior 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 exterior. [14]
Existe una noción de grado de planificación exterior. Una incrustación de un plano exterior de un gráfico es lo mismo que una incrustación de un plano exterior. Para k > 1, se dice que una incrustación plana es k -outerpillarlanar si la eliminación de los vértices de la cara exterior da como resultado una incrustación ( k - 1) -outerpillarlanar. Un gráfico es k -outerpillarlanar si tiene una incrustación k -outerpillarlanar. [15]
Se puede dibujar en un disco un gráfico exterior 1 plano , análogamente a los gráficos 1 plano , con los vértices en el límite del disco y con como máximo un cruce por borde.
Cada grafo del plano exterior máximo es un grafo cordal . Cada gráfico de plano exterior máximo es el gráfico de visibilidad de un polígono simple . [16] Las gráficas planas externas máximas también se forman como gráficas de triangulaciones poligonales . Son ejemplos de 2 árboles , de gráficos en serie-paralelos y de gráficos cordales .
Cada gráfico del plano exterior es un gráfico circular , el gráfico de intersección de un conjunto de cuerdas de un círculo. [17]
Notas
- ^ Felsner (2004) .
- ^ Chartrand y Harary (1967) ; Sysło (1979) ; Brandstädt, Le & Spinrad (1999) , Proposición 7.3.1, pág. 117; Felsner (2004) .
- ^ Diestel (2000) .
- ↑ a b Sysło (1979) .
- ^ Chartrand y Harary (1967) ; Sysło (1979) .
- ^ Li, Corneil y Mendelsohn (2000) , Proposición 2.5.
- ↑ a b Proskurowski y Sysło (1986) .
- ^ Fiorini (1975) .
- ^ Lamer y blanco (1970) .
- ^ Baker (1994) .
- ^ Scheinerman (1984) ; Brandstädt, Le y Spinrad (1999) , pág. 54.
- ^ Brandstädt, Le y Spinrad (1999) , p. 174.
- ^ Brandstädt, Le y Spinrad (1999) , p. 169.
- ^ Sysło y Proskurowski (1983) .
- ^ Kane y Basu (1976) ; Sysło (1979) .
- ^ El-Gindy (1985) ; Lin y Skiena (1995) ; Brandstädt, Le y Spinrad (1999) , Teorema 4.10.3, pág. sesenta y cinco.
- ^ Wessel y Pöschel (1985) ; Unger (1988) .
Referencias
- Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en gráficas planas", Journal of the ACM , 41 (1): 153–180, doi : 10.1145 / 174644.174650.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2004), "El problema de las incrustaciones externas en pseudosuperficies", Ars Combinatoria , 71 : 79–91.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2004), "Conjuntos de obstrucciones para gráficas de superficie exterior de banano", Ars Combinatoria , 73 : 65–77.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2006), "Gráficos incontables con todos sus vértices en una cara", Acta Mathematica Hungarica , 112 (4): 307–313, doi : 10.1007 / s10474-006-0082-0.
- Boza, Luis; Fedriani, Eugenio M .; Núñez, Juan (2010), "Capacidad de incrustación externa en ciertas pseudouperficies que surgen de tres esferas", Matemáticas discretas , 310 : 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 planares" , Annales de l'Institut Henri Poincaré B , 3 (4): 433–438, MR 0227041.
- Diestel, Reinhard (2000), Teoría de grafos , Textos de posgrado en matemáticas , 173 , Springer-Verlag, p. 107, ISBN 0-387-98976-5.
- El-Gindy, H. (1985), Descomposición jerárquica de polígonos con aplicaciones , Ph.D. tesis, Universidad McGill. Citado por Brandstädt, Le & Spinrad (1999) .
- Felsner, Stefan (2004), Gráficos y arreglos geométricos: algunos capítulos de geometría combinatoria , Vieweg + Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
- Fiorini, Stanley (1975), "Sobre el índice cromático de los gráficos planos externos", Journal of Combinatorial Theory , Serie B, 18 (1): 35–38, doi : 10.1016 / 0095-8956 (75) 90060-X.
- Fisk, Steve (1978), "Una breve prueba del teorema del vigilante de Chvátal", Journal of Combinatorial Theory , Serie B, 24 : 374, doi : 10.1016 / 0095-8956 (78) 90059-X.
- Fleischner, Herbert J .; Geller, DP; Harary, Frank (1974), "Gráficos planos exteriores y duales débiles", Revista de la Sociedad Matemática de la India , 38 : 215-219, MR 0389672.
- Kane, Vinay G .; Basu, Sanat K. (1976), "Sobre la profundidad de un gráfico plano", 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 completitud NP en gráficas planas", Matemáticas aplicadas discretas , 98 (3): 219-225, doi : 10.1016 / S0166-218X (99) 00163-8.
- Lick, Don R .; White, Arthur T. (1970), " k -degenerate graphs" , Canadian Journal of Mathematics , 22 : 1082–1096, doi : 10.4153 / CJM-1970-125-1.
- Lin, Yaw-Ling; Skiena, Steven S. (1995), "Aspectos de complejidad de los gráficos 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 bordes de gráficos planos externos", 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 gráfico , Ph.D. tesis, Universidad de Princeton. Citado por Brandstädt, Le & Spinrad (1999) .
- Sysło, Maciej M. (1979), "Caracterizaciones de gráficos planos externos", Matemáticas discretas , 26 (1): 47–53, doi : 10.1016 / 0012-365X (79) 90060-8.
- Sysło, Maciej M .; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Actas de una conferencia celebrada en Lagów, Polonia, del 10 al 13 de febrero de 1981 , Lecture Notes in Mathematics , 1018 , Springer-Verlag, págs. 248-256, doi : 10.1007 / BFb0071635.
- Unger, Walter (1988), "Sobre el color k de los gráficos circulares", Proc. Quinto Simposio sobre Aspectos Teóricos de la Informática (STACS '88) , Lecture Notes in Computer Science , 294 , Springer-Verlag, págs. 61–72, doi : 10.1007 / BFb0035832.
- Wessel, W .; Pöschel, R. (1985), "On circle graphs", en Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory celebrada en Eyba, 1 al 5 de octubre de 1984 , Teubner-Texte zur Mathematik, 73 , BG Teubner, págs. 207–210. Como lo cita Unger (1988) .
enlaces externos
- Gráficos exteriores en el sistema de información sobre clases de gráficos y sus inclusiones
- Weisstein, Eric W. "Gráfico Outplanar" . MathWorld .