En la teoría de grafos , el problema de prueba de planaridad es el problema algorítmico de probar si un gráfico dado es un gráfico plano (es decir, si se puede dibujar en el plano sin intersecciones de bordes). Este es un problema bien estudiado en informática para el cual han surgido muchos algoritmos prácticos , muchos de los cuales aprovechan estructuras de datos novedosas . La mayoría de estos métodos operan en tiempo O ( n ) (tiempo lineal), donde n es el número de aristas (o vértices) en el gráfico, que es asintóticamente óptimo. En lugar de ser solo un valor booleano único, la salida de un algoritmo de prueba de planaridad puede ser una incrustación de gráfico plano , si el gráfico es plano, o un obstáculo para la planaridad, como un subgráfico de Kuratowski , si no lo es.
Los algoritmos de prueba de planaridad suelen aprovechar los teoremas de la teoría de grafos que caracterizan el conjunto de gráficos planos en términos que son independientes de los dibujos de gráficos. Éstos incluyen
El criterio de planaridad de Fraysseix-Rosenstiehl puede usarse directamente como parte de algoritmos para pruebas de planaridad, mientras que los teoremas de Kuratowski y Wagner tienen aplicaciones indirectas: si un algoritmo puede encontrar una copia de K 5 o K 3,3 dentro de un gráfico dado, puede ser Asegúrese de que el gráfico de entrada no sea plano y regrese sin cálculos adicionales.
Otros criterios de planaridad, que caracterizan matemáticamente los gráficos planos pero son menos importantes para los algoritmos de prueba de planaridad, incluyen:
El método clásico de adición de rutas de Hopcroft y Tarjan [1] fue el primer algoritmo de prueba de planaridad de tiempo lineal publicado en 1974. En la Biblioteca de tipos y algoritmos de datos eficientes se proporciona una implementación del algoritmo de Hopcroft y Tarjan de Mehlhorn , Mutzel y Naher . [2] [3] [4] En 2012, Taylor [5] amplió este algoritmo para generar todas las permutaciones de orden de borde cíclico para incrustaciones planas de componentes biconectados.
Los métodos de suma de vértices funcionan manteniendo una estructura de datos que representa las posibles incrustaciones de un subgráfico inducido del gráfico dado y agregando vértices uno a la vez a esta estructura de datos. Estos métodos comenzaron con un método O( n 2 ) ineficiente concebido por Lempel , Even y Cederbaum en 1967. [6] Este fue mejorado por Even y Tarjan, quienes encontraron una solución de tiempo lineal para el paso de numeración s , t , [ 7] y por Booth y Lueker , quienes desarrollaron el árbol PQestructura de datos. Con estas mejoras, es de tiempo lineal y supera al método de adición de rutas en la práctica. [8] Este método también se amplió para permitir que una incrustación plana (dibujo) se calcule de manera eficiente para un gráfico plano. [9] En 1999, Shih y Hsu simplificaron estos métodos utilizando el árbol PC (una variante no arraigada del árbol PQ) y un recorrido posterior al orden del árbol de búsqueda en profundidad de los vértices. [10]