En 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 simplemente 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 subgrafo 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. Éstas 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 determinado, 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 que son menos centrales para los algoritmos de prueba de planaridad, incluyen:
El método clásico de suma de rutas de Hopcroft y Tarjan [1] fue el primer algoritmo de prueba de planaridad en tiempo lineal publicado en 1974. Se proporciona una implementación del algoritmo de Hopcroft y Tarjan en la Biblioteca de algoritmos y tipos de datos eficientes de Mehlhorn , Mutzel y Naher. [2] [3] [4] En 2012, Taylor [5] amplió este algoritmo para generar todas las permutaciones de orden de aristas cíclicas 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 subgrafo inducido del gráfico dado y agregando vértices uno por uno a esta estructura de datos. Estos métodos comenzaron con un método ineficiente O ( n 2 ) 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 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 sin raíz del árbol PQ) y un recorrido en 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 bordes para calcular una incrustación plana, 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 Méndez y Rosenstiehl [12] [13] ). Véase [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 amplió para extraer múltiples subdivisiones de Kuratowski de un gráfico de entrada no plano en un tiempo de ejecución que depende linealmente 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 localizan 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 gráficos de 3 conexos para construir incrementalmente incrustaciones planas de cada componente de 3 conexos 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 gráfico intermedio en el camino hacia el componente completo sea nuevamente conexo 3. Dado que tales gráficos tienen una incrustación única (hasta el volteo y la elección de la cara externa), el siguiente gráfico más grande, si aún es plano, debe ser un refinamiento del gráfico anterior. Esto permite reducir la prueba de planaridad a simplemente 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 proporciona un tiempo de ejecución lineal), el método en sí adolece de la complejidad de encontrar la secuencia de construcción.
Las pruebas de planaridad se han 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 gráfico sufre actualizaciones locales, generalmente en forma de inserción/eliminación de aristas. En el caso de llegada de borde, 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 totalmente dinámico en el que se insertan y eliminan bordes, 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] mejorando los algoritmos de tiempo de actualización sublineal de Eppstein , Galil , Italiano , Sarnak y Spencer. [26] [27]