En teoría de grafos , el problema de prueba de planaridad es el problema algorítmico de probar si un grafo dado es un grafo planar (es decir, si se puede dibujar en el plano sin intersecciones de aristas). Este es un problema bien estudiado en informática para el que han surgido muchos algoritmos prácticos , muchos de los cuales aprovechan nuevas estructuras de datos . 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 grafo, que es asintóticamente óptimo . En lugar de ser simplemente un único valor booleano, la salida de un algoritmo de prueba de planaridad puede ser una incrustación de grafo planar , si el grafo es planar, o un obstáculo para la planaridad, como un subgrafo de Kuratowski, si no lo es.
Los algoritmos de prueba de planaridad generalmente aprovechan los teoremas de la teoría de grafos que caracterizan el conjunto de grafos planares en términos que son independientes de los dibujos de grafos. Estos incluyen:
El criterio de planaridad de Fraysseix-Rosenstiehl se puede utilizar 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 estar seguro de que el gráfico de entrada no es planar y regresar sin cálculos adicionales.
Otros criterios de planaridad, que caracterizan matemáticamente a los gráficos planares pero que son menos centrales 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 en tiempo lineal publicado en 1974. Una implementación del algoritmo de Hopcroft y Tarjan se proporciona en la Biblioteca de tipos de datos y algoritmos eficientes de Mehlhorn , Mutzel y Näher. [2] [3] [4] En 2012, Taylor [5] extendió este algoritmo para generar todas las permutaciones de orden de borde cíclico para incrustaciones planas de componentes biconectados.
Los métodos de adición de vértices funcionan manteniendo una estructura de datos que representa las posibles incrustaciones de un subgrafo inducido del grafo dado y añadiendo 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] 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 la estructura de datos del árbol PQ . Con estas mejoras es de tiempo lineal y supera al método de adición de caminos en la práctica. [8] Este método también se extendió para permitir que una incrustación planar (dibujo) se calcule de manera eficiente para un grafo planar. [9] En 1999, Shih y Hsu simplificaron estos métodos utilizando el árbol PC (una variante sin raíz del árbol PQ) y un recorrido de postorden del árbol de búsqueda en profundidad de los vértices. [10]
En 2004, John Boyer y Wendy Myrvold [11] desarrollaron un algoritmo O( n ) simplificado , originalmente inspirado en el método del árbol PQ, que elimina el árbol PQ y utiliza adiciones de aristas para calcular una incrustación planar, si es posible. De lo contrario, se calcula una subdivisión de Kuratowski (de K 5 o K 3,3 ). Este es uno de los dos algoritmos de última generación actuales (el otro es el algoritmo de prueba de planaridad de de Fraysseix, Ossona de Mendez y Rosenstiehl [12] [13] ). Consulte [14] para una comparación experimental con una versión preliminar de la prueba de planaridad de Boyer y Myrvold. Además, la prueba de Boyer-Myrvold se extendió para extraer múltiples subdivisiones de Kuratowski de un grafo de entrada no planar en un tiempo de ejecución linealmente dependiente del tamaño de salida. [15] El código fuente para la prueba de planaridad [16] [17] y la extracción de múltiples subdivisiones de Kuratowski [16] está disponible públicamente. Williamson desarrolló algoritmos que ubican un subgrafo de Kuratowski en tiempo lineal en los vértices en la década de 1980. [18]
Un método diferente utiliza una construcción inductiva de grafos 3-conectados para construir de manera incremental incrustaciones planas de cada componente 3-conectado de G (y, por lo tanto, una incrustación plana de G en sí). [19] La construcción comienza con K 4 y se define de tal manera que cada grafo intermedio en el camino hacia el componente completo es nuevamente 3-conectado. Dado que dichos grafos tienen una incrustación única (hasta el giro y la elección de la cara externa), el siguiente grafo más grande, si aún es planar, debe ser un refinamiento del grafo anterior. Esto permite reducir la prueba de planaridad a solo probar en cada paso si el siguiente borde agregado tiene ambos extremos en la cara externa de la incrustación actual. Si bien esto es conceptualmente muy simple (y brinda un tiempo de ejecución lineal), el método en sí mismo sufre la complejidad de encontrar la secuencia de construcción.
La prueba de planaridad se ha estudiado en el modelo de algoritmos dinámicos , en el que se mantiene una respuesta a un problema (en este caso, planaridad) a medida que el grafo sufre actualizaciones locales, típicamente en forma de inserción/eliminación de aristas. En el caso de llegada de aristas, existe un algoritmo de tiempo de actualización de función de Ackermann inversa asintóticamente ajustado debido a La Poutré, [20] que mejora los algoritmos de Di Battista, Tamassia y Westbrook. [21] [22] [23] En el caso completamente dinámico donde se insertan y eliminan aristas, existe un límite inferior de tiempo de actualización logarítmico de Pătrașcu y Demaine , [24] y un algoritmo de tiempo de actualización polilogarítmico de Holm y Rotenberg, [25] que mejora los algoritmos de tiempo de actualización sublineales de Eppstein , Galil , Italiano , Sarnak y Spencer. [26] [27]