Pruebas de planitud

El método clásico de adición de caminos de Hopcroft y Tarjan ^{[ 1 ]} fue el primer algoritmo de prueba de planaridad de 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 del orden de aristas cíclicas para incrustaciones planas de componentes biconexas.

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 agregando vértices uno por uno a esta estructura de datos. Estos métodos comenzaron con un método ineficiente O( n² ^{) 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 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, inspirado originalmente 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 ₅ o K _3,3 ). Este es uno de los dos algoritmos de vanguardia 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 extendió para extraer múltiples subdivisiones de Kuratowski de un grafo de entrada no planar en un tiempo de ejecución que depende linealmente del tamaño de la 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. Los algoritmos que localizan un subgrafo de Kuratowski en tiempo lineal en vértices fueron desarrollados por Williamson en la década de 1980. ^{[ 18 ]}

Un método diferente utiliza una construcción inductiva de grafos 3-conectados para construir incrementalmente incrustaciones planas de cada componente 3-conectado de G (y por lo tanto una incrustación plana de G mismo). ^{[ 19 ]} La construcción comienza con K ₄ y se define de tal manera que cada grafo intermedio en el camino hacia el componente completo es nuevamente 3-conectado. Dado que tales grafos tienen una incrustación única (salvo inversión y 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 simplemente comprobar para cada paso si la siguiente arista agregada tiene ambos extremos en la cara externa de la incrustación actual. Si bien esto es conceptualmente muy simple (y da un tiempo de ejecución lineal), el método en sí sufre de 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) mientras el grafo sufre actualizaciones locales, típicamente en forma de inserción/eliminación de aristas. En el caso de llegada de aristas, hay un algoritmo de tiempo de actualización de función de Ackermann inversa asintóticamente ajustado debido a La Poutré , ^{[ 20 ]} mejorando los algoritmos de Di Battista, Tamassia y Westbrook. ^{[ 21 ] [ 22 ] [ 23 ]} En el caso totalmente dinámico donde las aristas se insertan y eliminan, hay una cota inferior de tiempo de actualización logarítmica por Pătrașcu y Demaine , ^{[ 24 ]} y un algoritmo de tiempo de actualización polilogarítmico por Holm y Rotenberg , ^{[ 25 ]} mejorando los algoritmos de tiempo de actualización sublineales de Eppstein , Galil , Italiano , Sarnak y Spencer. ^{[ 26 ] [ 27 ]}