Planarización

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 puede realizarse utilizando cualquier método para encontrar un dibujo (con intersecciones) del grafo dado, y luego reemplazando cada punto de intersección por un nuevo vértice artificial , lo que provoca que cada arista cruzada se subdivida en un camino . El grafo original se representará como un menor de inmersión 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 no forman parte de este subgrafo se agregan una a una 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 ubicado 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 el dibujo de grafos es más efectivo cuando el primer paso del proceso encuentra el grafo planar 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-difícil y MaxSNP-difícil , lo que implica que probablemente no exista un algoritmo de tiempo polinomial que resuelva el problema exactamente 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 tratable de parámetro fijo 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 grafo. ^{[ 3 ] [ 7 ]}     

También se ha estudiado un problema relacionado: encontrar el subgrafo inducido planar más grande de un grafo dado. Nuevamente, este problema es NP-difícil, pero tratable con parámetros fijos cuando todos los vértices, excepto unos pocos, pertenecen al subgrafo inducido. ^{[ 8 ]} Edwards y Farr (2002) demostraron una cota ajustada de 3 n /(Δ  +  1) para el tamaño del subgrafo inducido planar más grande, en función de n , el número de vértices en el grafo dado, y Δ, su grado máximo ; su demostración conduce a un algoritmo de tiempo polinomial para encontrar un subgrafo inducido de este tamaño. ^{[ 9 ]}

Una vez encontrado un subgrafo planar grande, el proceso de planarización incremental continúa considerando las aristas restantes una por una. Al hacerlo, 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 el orden como una permutación aleatoria , ejecutando el mismo algoritmo varias veces y devolviendo la mejor planarización que encuentra. ^{[ 1 ]}

En la forma más simple de este proceso, la incrustación planar del subgrafo planarizado no puede cambiar mientras se agregan nuevas aristas. Para agregar cada nueva arista de manera que se minimice el número de cruces que forma, se puede usar un algoritmo de camino más corto en el grafo dual de la incrustación actual, para encontrar la secuencia más corta de caras de la incrustación y aristas que se deben cruzar y que conecta los extremos de la nueva arista entre sí. Este proceso toma tiempo polinomial por arista. ^{[ 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 formados al añadir una arista a un subgrafo planar, donde el dibujo óptimo tiene solo 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 entre todas las incrustaciones del subgrafo planarizado y encontrar la que minimiza el número de cruces formados por la nueva arista. ^{[ 1 ] [ 10 ]}