Un gráfico de tres planos exteriores, el gráfico de un dodecaedro rómbico . Hay cuatro vértices en la cara exterior, ocho vértices en la segunda capa (amarillo claro) y dos vértices en la tercera capa (amarillo más oscuro). Debido a las simetrías del gráfico, ninguna otra incrustación tiene menos capas.
En teoría de grafos , un grafo k -externoplanar es un grafo plano que tiene una incrustación plana en la que los vértices pertenecen a capas concéntricas como máximo. El índice de externoplanaridad de un grafo plano es el valor mínimo para el cual es externoplanar.
Definición
Un grafo exterior-planar (o grafo 1-exterior-planar) tiene todos sus vértices en la cara no acotada (externa) del grafo. Un grafo 2-exterior-planar es un grafo plano con la propiedad de que, cuando se eliminan los vértices de la cara no acotada, los vértices restantes se encuentran todos en la cara no acotada recién formada. Y así sucesivamente.
Más formalmente, un grafo es -externoplanar si tiene una incrustación plana tal que, para cada vértice, hay una secuencia alternada de como máximo caras y vértices de la incrustación, comenzando con la cara ilimitada y terminando con el vértice, en la que cada cara y vértice consecutivos son incidentes entre sí.
Propiedades y aplicaciones
Los grafos -outerplanares tienen un ancho de árbol como máximo . [1] Sin embargo, algunos grafos planares con un ancho de árbol acotado, como el grafo de triángulos anidados, pueden ser -outerplanares solo para , lineales en el número de vértices, muy grandes.
La técnica de Baker cubre un gráfico planar con un número constante de gráficos -externoplanares y utiliza su bajo ancho de árbol para aproximarse rápidamente a varios problemas difíciles de optimización de gráficos. [2]
En relación con la conjetura GNRS sobre la incrustación métrica de familias de gráficos menores cerrados, los gráficos -externoplanares son una de las clases más generales de gráficos para las que se ha demostrado la conjetura. [3]
Se ha demostrado una conjetura inversa del teorema de Courcelle , según la cual cada propiedad gráfica reconocible en gráficos de ancho de árbol acotado por autómatas de árboles de estados finitos es definible en la lógica monádica de segundo orden de gráficos , para los gráficos -externoplanares. [4]
Reconocimiento
El valor más pequeño de para el cual un gráfico dado es -exteriormente planar (su índice de exteriormente planar) se puede calcular en tiempo cuadrático. [5]
Referencias
^ Bodlaender, Hans L. (1998), "Un arboreto parcial de gráficos con ancho de árbol acotado", Theoretical Computer Science , 209 (1–2): 1–45, doi :10.1016/S0304-3975(97)00228-4, hdl : 1874/18312 , MR 1647486
^ Baker, B. (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.
^ Chekuri, Chandra; Gupta, Anupam; Newman, Ilán; Rabinovich, Yuri; Sinclair, Alistair (2006), "Incrustación de gráficos planos externos en ", Revista SIAM de Matemáticas Discretas , 20 (1): 119–136, doi :10.1137/S0895480102417379, MR 2257250, S2CID 13925350
^ Jaffke, Lars; Bodlaender, Hans L .; Heggernes, Pinar ; Telle, Jan Arne (2017), "La definibilidad es igual a la reconocibilidad de los gráficos k {\displaystyle k} -externoplanares y los árboles k {\displaystyle k} -cordales parciales ℓ {\displaystyle \ell }" (PDF) , European Journal of Combinatorics , 66 : 191–234, doi : 10.1016/j.ejc.2017.06.025 , MR 3692146
^ Kammer, Frank (2007), "Determinación del menor de los que son -outerplanar", en Arge, Lars; Hoffmann, Michael; Welzl, Emo (eds.), Algorithms: ESA 2007, 15th Annual European Symposium, Eilat, Israel, 8-10 de octubre de 2007, Actas , Lecture Notes in Computer Science, vol. 4698, Springer, págs. 359–370, doi :10.1007/978-3-540-75520-3_33
