En el campo matemático de la teoría de grafos , la planarización es un método para extender los métodos de dibujo de grafos desde grafos planares a grafos que no son planares, mediante la incrustación de los grafos no planares dentro de un grafo planar más grande. [1] [2]
La planarización se puede realizar utilizando cualquier método para encontrar un dibujo (con cruces) para el grafo dado y luego reemplazar cada punto de cruce por un nuevo vértice artificial , haciendo que cada arista cruzada se subdivida en un camino . El grafo original se representará como una inmersión menor de su planarización.
En la planarización incremental , el proceso de planarización se divide en dos etapas. Primero, se encuentra un subgrafo planar grande dentro del grafo dado. Luego, las aristas restantes que aún no son parte de este subgrafo se agregan de a una por vez y se enrutan a través de una incrustación del subgrafo planar. Cuando una de estas aristas cruza una arista ya incrustada, las dos aristas que se cruzan se reemplazan por caminos de dos aristas, con un nuevo vértice artificial que representa el punto de cruce colocado en el medio de ambos caminos. [1] [2] En algunos casos, se agrega una tercera etapa de optimización local al proceso de planarización, en la que las aristas con muchos cruces se eliminan y se vuelven a agregar en un intento de mejorar la planarización. [1]
El uso de la planarización incremental para dibujar gráficos es más eficaz cuando el primer paso del proceso encuentra un gráfico planar lo más grande posible. Desafortunadamente, encontrar el subgrafo planar con el número máximo posible de aristas (el problema del subgrafo planar máximo [3] ) es NP-hard y MaxSNP-hard , lo que implica que probablemente no exista un algoritmo de tiempo polinomial que resuelva el problema de manera exacta o que lo aproxime arbitrariamente bien. [4]
En un grafo conexo de n vértices , el subgrafo planar más grande tiene como máximo 3 n − 6 aristas, y cualquier árbol de expansión forma un subgrafo planar con n − 1 aristas. Por lo tanto, es fácil aproximar el subgrafo planar máximo dentro de una razón de aproximación de un tercio, simplemente encontrando un árbol de expansión. Se conoce una razón de aproximación mejor, 9/4, basada en un método para encontrar un 2-árbol parcial grande como un subgrafo del grafo dado. [1] [4] Alternativamente, si se espera que el subgrafo planar incluya casi todas las aristas del grafo dado, dejando solo un pequeño número k de aristas no planas para el proceso de planarización incremental, entonces se puede resolver el problema exactamente usando un algoritmo manejable de parámetros fijos cuyo tiempo de ejecución es lineal en el tamaño del grafo pero no polinomial en el parámetro k . [5] El problema también puede resolverse exactamente mediante un algoritmo de ramificación y corte , sin garantías en el tiempo de ejecución, pero con un buen rendimiento en la práctica. [1] [6] Este parámetro k se conoce como la asimetría del gráfico. [3] [7]
También se ha estudiado un problema relacionado, el de encontrar el subgrafo inducido planar más grande de un grafo dado. Nuevamente, esto es NP-hard, pero manejable con parámetros fijos cuando todos los vértices, excepto unos pocos, pertenecen al subgrafo inducido. [8] Edwards y Farr (2002) demostraron un límite estricto de 3 n /(Δ + 1) para el tamaño del subgrafo inducido planar más grande, como una función de n , el número de vértices en el grafo dado, y Δ, su grado máximo ; su prueba conduce a un algoritmo de tiempo polinomial para encontrar un subgrafo inducido de este tamaño. [9]
Una vez que se ha encontrado un subgrafo planar grande, el proceso de planarización incremental continúa considerando las aristas restantes una por una. A medida que lo hace, mantiene una planarización del subgrafo formado por las aristas que ya se han considerado. Agrega cada nueva arista a una incrustación planar de este subgrafo, formando un dibujo con cruces, y luego reemplaza cada punto de cruce con un nuevo vértice artificial que subdivide las dos aristas que se cruzan. [1] [2] En algunas versiones de este procedimiento, el orden para agregar aristas es arbitrario, pero también es posible elegir que el orden sea una permutación aleatoria , ejecutando el mismo algoritmo varias veces y devolviendo la mejor planarización que encuentre. [1]
En la forma más simple de este proceso, no se permite que la incrustación planar del subgrafo planarizado cambie mientras se agregan nuevos bordes. Para agregar cada nuevo borde de una manera que minimice la cantidad de cruces que forma, se puede usar un algoritmo de ruta más corta en el grafo dual de la incrustación actual, para encontrar la secuencia más corta de caras de la incrustación y bordes que se cruzarán que conectan los puntos finales del nuevo borde entre sí. Este proceso toma un tiempo polinomial por borde. [2]
Fijar la incrustación del subgrafo planarizado no es necesariamente óptimo en términos del número de cruces resultantes. De hecho, existen grafos que se forman añadiendo una arista a un subgrafo planar, donde el dibujo óptimo tiene sólo dos cruces pero donde fijar la incrustación planar del subgrafo obliga a crear un número lineal de cruces. [1] Como compromiso entre encontrar la planarización óptima de un subgrafo planar más una arista y mantener una incrustación fija, es posible buscar sobre todas las incrustaciones del subgrafo planarizado y encontrar aquella que minimice el número de cruces formados por la nueva arista. [1] [10]