k-grafo plano exterior
En teoría de grafos , un grafo k -outerpillarlanar es un grafo plano que tiene una incrustación plana en la que los vértices pertenecen como máximo a capas concéntricas. El índice de planaridad exterior de un gráfico plano es el valor mínimo para el que es -outerpillarlanar.
Un gráfico plano exterior (o gráfico 1-plano exterior) tiene todos sus vértices en la cara no acotada (exterior) del gráfico. Un gráfico de 2 planos exteriores es un gráfico plano con la propiedad de que, cuando se eliminan los vértices de la cara ilimitada, los vértices restantes se encuentran todos en la cara ilimitada recién formada. Y así.
Más formalmente, una gráfica es -outerpillarlanar si tiene una incrustación plana tal que, para cada vértice, hay una secuencia alterna de como máximo las caras y vértices de la incrustación, comenzando con la cara ilimitada y terminando con el vértice, en el que cada La cara y el vértice consecutivos son incidentes entre sí.
Los gráficos planos-oruga tienen un ancho de árbol como máximo . [1] Sin embargo, algunos gráficos planos de ancho de árbol delimitado, como el gráfico de triángulos anidados, pueden ser planos sólo para muy grandes , lineales en el número de vértices.
La técnica de Baker cubre un gráfico plano con un número constante de gráficos planos-oruga y utiliza su ancho de árbol bajo para aproximar rápidamente varios problemas de optimización de gráficos duros. [2]
En relación con la conjetura de GNRS sobre la incrustación métrica de familias de grafos cerrados menores, los grafos planos-oruga son una de las clases más generales de grafos para los que se ha probado la conjetura. [3]
