grafo k -exterior planar

En teoría de grafos , un grafo k -exterior planar es un grafo planar que tiene una incrustación planar en la que los vértices pertenecen a como máximo${\displaystyle k}$capas concéntricas. El índice de planaridad externa de un grafo planar es el valor mínimo de${\displaystyle k}$para lo cual es${\displaystyle k}$-planar externo.

Un grafo planar exterior (o grafo 1-planar exterior) tiene todos sus vértices en la cara no acotada (exterior) del grafo. Un grafo 2-planar exterior es un grafo planar cuya propiedad es tal que, al eliminar los vértices de la cara no acotada, los vértices restantes se encuentran todos en la nueva cara no acotada. Y así sucesivamente.

Más formalmente, un gráfico es${\displaystyle k}$-outerplanar si tiene una incrustación planar tal que, para cada vértice, hay una secuencia alternada de como máximo${\displaystyle k}$caras y${\displaystyle k}$vértices de la incrustación, comenzando con la cara no delimitada y terminando con el vértice, en el que cada cara y vértice consecutivos son incidentes entre sí.

El${\displaystyle k}$-Los grafos planares externos tienen un ancho de árbol como máximo${\displaystyle 3k-1}$. ^{[ 1 ]} Sin embargo, algunos grafos planares de ancho de árbol limitado, como el grafo de triángulos anidados, pueden ser${\displaystyle k}$-Outerplanar solo para muy grandes${\displaystyle k}$, lineal en el número de vértices.

La técnica de Baker cubre un gráfico planar con un número constante de${\displaystyle k}$-grafos outerplanares y utiliza su bajo ancho de árbol para aproximar rápidamente varios problemas difíciles de optimización de grafos. ^{[ 2 ]}

En relación con la conjetura GNRS sobre la incrustación métrica de familias de grafos cerrados menores, la${\displaystyle k}$Los grafos -outerplanares son una de las clases más generales de grafos para las cuales se ha demostrado la conjetura. ^{[ 3 ]}

Se ha demostrado para el caso una conjetura recíproca del teorema de Courcelle , según la cual toda propiedad gráfica reconocible en grafos 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 grafos .${\displaystyle k}$-grafos exteriores planares. ^{[ 4 ]}

El valor más pequeño de${\displaystyle k}$para el cual se da un gráfico${\displaystyle k}$-outerplanar (su índice de planaridad externa) se puede calcular en tiempo cuadrático. ^{[ 5 ]}