El problema de la planaridad es el problema algorítmico de verificar si un gráfico dado es plano (es decir, si se puede dibujar en un plano sin cruzar los bordes). El problema está bien estudiado en informática y se han inventado muchos algoritmos prácticos para resolverlo, muchos de los cuales utilizan estructuras de datos modernas . La mayoría de estos métodos se ejecutan en tiempo O( n ) (tiempo lineal), donde n es el número de aristas (o vértices) del gráfico, que es un algoritmo asintóticamente óptimo . En lugar de un valor booleano simple, la salida de los algoritmos de verificación de planaridad puede generar una incrustación de gráfico si el gráfico es plano, o una cobertura de planaridad como un subgráfico de Kuratowski si el gráfico no es plano.
Los algoritmos de prueba de planaridad generalmente usan teoremas de teoría de gráficos que describen el conjunto de gráficos planos en términos que son independientes del dibujo del gráfico. Esto incluye
El criterio de planaridad de De Fraisex-Rosenstil se puede usar directamente como parte del algoritmo de prueba de planaridad, mientras que los teoremas de Kuratowski y Wagner se aplican indirectamente: si el algoritmo puede encontrar una copia de K 5 o K 3,3 en un gráfico dado, uno puede estar seguro de que el gráfico de entrada no es plano
Otros criterios de planaridad que describen gráficos planos matemáticamente, pero que son menos adecuados para los algoritmos de prueba de planaridad, incluyen el criterio de planaridad de Whitney , que un gráfico es plano si y solo si su gráfico matroid también es cograph, el criterio de planaridad de McLane , que describe los gráficos planos por bases de sus espacios cíclicos , el teorema de Schneider , que describe grafos planos con la dimensión de orden conjuntos parcialmente ordenados asociados , y el criterio de planaridad de Colin de Verdière , utilizando la teoría de grafos espectrales .
El primer algoritmo de verificación de planaridad publicado (en 1974) fue el método clásico de suma de rutas de Hopcroft y Tarjan [1] , que se ejecutaba en tiempo lineal. La implementación del algoritmo de Hopcroft y Tarjan se incluye en la biblioteca de algoritmos y tipos de datos efectivos Mehlhorn , Muzel y Neher [2] [3] [4] . En 2012, Taylor [5] amplió este algoritmo para generar todas las permutaciones de órdenes de aristas cíclicas para incrustar componentes doblemente conectados.
Un método para agregar vértices mediante la creación de una estructura de datos que representa los posibles anidamientos de un subgráfico generado de un gráfico dado y agregar vértices uno a la vez a esta estructura de datos. Estos métodos comenzaron con el ineficiente método O( n 2 ) propuesto por Lempel , Ewen y Zederbaum en 1967 [6] . El método fue mejorado por Ewen y Tarjan, quienes encontraron una solución de tiempo lineal para el paso s , numeración t [7] , y luego mejorado por Booth y Luker, quienes desarrollaron la estructura de datos de árbol PQ . Con estas mejoras, el método se volvió lineal en el tiempo y, en la práctica, comenzó a funcionar más rápido que el método de agregar caminos [8] . Este método también se ha ampliado para calcular de manera eficiente la incrustación plana (dibujo) para gráficos planos [9] . En 1999, Shi y Xu simplificaron estos métodos utilizando un árbol PC (una versión no rooteada del árbol PQ) y un recorrido de árbol de vértice retardado con búsqueda en profundidad [10] .
En 2004, Boyer y Myhrvold [11] desarrollaron un algoritmo simplificado con tiempo de ejecución O( n ), que se inspiró en el método del árbol PQ, pero en el que se descartó el árbol PQ y el algoritmo usa la suma de aristas para calcular una incrustación plana, si es posible. De lo contrario, se calcula la subdivisión de Kuratowski (ya sea el gráfico K 5 o el gráfico K 3,3 ). El método es uno de los dos algoritmos existentes actualmente (el otro es el algoritmo de verificación de planaridad de Freisex, de Mendes y Rosenstiel [12] [13] ). Ver Boyer, Cortese, Patrignami y Battista [14] para una comparación experimental con una versión preliminar del algoritmo de verificación de planaridad de Boyer y Myhrvold. Al mismo tiempo, el algoritmo de verificación de Boyer y Myhrvold se amplió para extraer varias subdivisiones del gráfico de entrada no plano de Kuratov con un tiempo de ejecución linealmente dependiente del tamaño de salida [15] . Los códigos fuente para la comprobación de planaridad [16] [17] y la selección de varias subdivisiones de Kuratovsky [16] son de dominio público (en C++). Un algoritmo que determina el subgrafo de Kuratowski en el tiempo lineal en el número de vértices fue desarrollado por Williamson en la década de 1980 [18] .
Otro método utiliza la construcción de gráficos 3-conectados por inducción para construir secuencialmente una incrustación plana de cualquier componente 3-conectado del gráfico G (y por lo tanto una incrustación plana del propio gráfico G ) [19] . La construcción comienza desde K 4 y se define de tal manera que cualquier gráfico intermedio en el camino hacia el componente completo es nuevamente 3-conexo. Dado que tales gráficos tienen una sola incrustación (hasta la elección de una cara exterior), el siguiente gráfico más grande, si permanece plano, debe ser un refinamiento del gráfico anterior. Esto reduce la prueba de planaridad a simplemente verificar si el siguiente borde agregado tendrá ambos extremos en la cara exterior del anidamiento actual. Siendo conceptualmente muy simple (y da un tiempo de ejecución lineal), el método tiene mucha complejidad para encontrar la secuencia de construcción.