En el dibujo de gráficos , la planarización es un método para extender los métodos de dibujo de gráficos planos a gráficos que no son planos, al incorporar los gráficos no planos dentro de un gráfico plano más grande. [1] [2]
La planarización se puede realizar utilizando cualquier método para encontrar un dibujo (con cruces) para el gráfico dado y luego reemplazando cada punto de cruce por un nuevo vértice artificial, lo que hace que cada borde cruzado se subdivida en una ruta. 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 plano grande dentro del grafo dado. Luego, los bordes restantes que aún no forman parte de este subgrafo se vuelven a agregar uno a la vez y se enrutan a través de una incrustación del subgrafo plano. 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 situado en el medio de ambas rutas. [1] [2] En algunos casos, se agrega una tercera etapa de optimización local al proceso de planarización, en la que los bordes con muchos cruces se eliminan y se vuelven a agregar en un intento por mejorar la planarización. [1]
El uso de planarización incremental para el dibujo de gráficos es más efectivo cuando el primer paso del proceso encuentra un gráfico plano tan grande como sea posible. Desafortunadamente, encontrar el subgrafo planar con el máximo número 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 exactamente o que se aproxima arbitrariamente bien. [4]
En un gráfico conectado de n vértices, el subgráfico plano más grande tiene como máximo 3 n − 6 aristas, y cualquier árbol de expansión forma un subgráfico plano con n − 1 aristas. Por lo tanto, es fácil aproximar el subgrafo planar máximo dentro de una relación de aproximación de un tercio, simplemente encontrando un árbol de expansión. Se conoce una mejor relación de aproximación, 9/4, basada en un método para encontrar un árbol 2 parcial grande como un subgráfico del gráfico dado. [1] [4] Alternativamente, si se espera que el subgrafo plano incluya casi todos los bordes del gráfico dado, dejando solo un pequeño número kde bordes no planos para el proceso de planarización incremental, entonces uno puede resolver el problema exactamente usando un algoritmo manejable de parámetro fijo cuyo tiempo de ejecución es lineal en el tamaño del gráfico 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 sobre 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 realizado algún estudio de un problema relacionado, encontrar el subgrafo inducido plano más grande de un gráfico dado. Nuevamente, esto es NP-duro, pero tratable 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 estrecho de 3 n /(Δ + 1) en el tamaño del subgrafo inducido plano más grande, en función de n , el número de vértices en el gráfico 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]