Teorema del separador planar

Lipton y Tarjan (1979) aumentan el grafo planar dado con aristas adicionales, si es necesario, para que se convierta en planar máximo (cada cara en una incrustación planar es un triángulo). Luego realizan una búsqueda en anchura , con raíz en un vértice arbitrario.${\displaystyle v}$y dividir los vértices en niveles según su distancia desde${\displaystyle v}$. Si${\displaystyle l_{1}}$es el nivel medio (el nivel tal que el número de vértices en niveles superiores e inferiores es como máximo)${\displaystyle n/2}$) entonces debe haber niveles${\displaystyle l_{0}}$y${\displaystyle l_{2}}$que son${\displaystyle O({\sqrt {n}})}$escalones arriba y abajo${\displaystyle l_{1}}$respectivamente y que contienen${\displaystyle O({\sqrt {n}})}$vértices, respectivamente, porque de lo contrario habría más de${\displaystyle n}$vértices en los niveles cercanos${\displaystyle l_{1}}$Demuestran que debe haber un separador.${\displaystyle S}$formada por la unión de${\displaystyle l_{0}}$y${\displaystyle l_{2}}$, los extremos de una arista${\displaystyle e}$de${\displaystyle G}$que no pertenece al árbol de búsqueda en anchura y que se encuentra entre los dos niveles, y los vértices en las dos rutas del árbol de búsqueda en anchura desde los puntos finales de${\displaystyle e}$volver a subir al nivel${\displaystyle l_{0}}$. El tamaño del separador${\displaystyle S}$construido de esta manera es como máximo${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$. Los vértices del separador y los dos subgrafos disjuntos se pueden encontrar en tiempo lineal . ^{[ 4 ]}

Esta demostración del teorema del separador también se aplica a grafos planares ponderados, en los que cada vértice tiene un coste no negativo. El grafo puede particionarse en tres conjuntos.${\displaystyle A}$,${\displaystyle S}$, y${\displaystyle B}$de tal manera que${\displaystyle A}$y${\displaystyle B}$cada uno tiene como máximo${\displaystyle 2/3}$del costo total y${\displaystyle S}$tiene${\displaystyle O({\sqrt {n}})}$vértices, sin aristas de${\displaystyle A}$y${\displaystyle B}$. ^{[ 4 ]} Al analizar con más detenimiento una construcción de separador similar, Djidjev (1982) muestra que el límite en el tamaño de${\displaystyle S}$puede reducirse a${\displaystyle {\sqrt {6n}}\approx 2.45{\sqrt {n}}}$. ^{[ 2 ]}

Holzer et al. (2009) sugieren una versión simplificada de este enfoque: amplían el grafo para que sea planar máximo y construyen un árbol de búsqueda en anchura como antes. Luego, para cada arista${\displaystyle e}$que no es parte del árbol, forman un ciclo al combinarse${\displaystyle e}$con la ruta del árbol que conecta sus extremos. Luego usan como separador los vértices de uno de estos ciclos. Aunque no se puede garantizar que este enfoque encuentre un separador pequeño para grafos planares de alto diámetro, sus experimentos indican que supera a los métodos de capas de Lipton-Tarjan y Djidjev de búsqueda en anchura en muchos tipos de grafos planares. ^{[ 5 ]}

Para un grafo que ya es maximal planar, es posible mostrar una construcción más fuerte de un separador de ciclos simple , un ciclo de longitud pequeña tal que el interior y el exterior del ciclo (en la incrustación planar única del grafo) tienen cada uno como máximo${\displaystyle 2n/3}$vértices. Miller (1986) demuestra esto (con un tamaño de separador de${\displaystyle {\sqrt {8n}}}$) mediante el uso de la técnica Lipton-Tarjan para una versión modificada de la búsqueda en amplitud en la que los niveles de la búsqueda forman ciclos simples. ^{[ 6 ]}

Alon, Seymour y Thomas (1994) demuestran la existencia de separadores de ciclos simples de forma más directa: sea${\displaystyle C}$ser un ciclo de como máximo${\displaystyle {\sqrt {8n}}}$vértices, con como máximo${\displaystyle 2n/3}$vértices externos${\displaystyle C}$, que forma una partición lo más uniforme posible entre el interior y el exterior. Demuestran que estas suposiciones obligan${\displaystyle C}$ser un separador. Porque de lo contrario, las distancias dentro${\displaystyle C}$debe ser igual a las distancias en el disco encerrado por${\displaystyle C}$(un camino más corto a través del interior del disco formaría parte del límite de un mejor ciclo). Además,${\displaystyle C}$debe tener la longitud exacta${\displaystyle {\sqrt {8n}}}$, ya que de lo contrario podría mejorarse reemplazando uno de sus bordes por los otros dos lados de un triángulo. Si los vértices en${\displaystyle C}$están numerados (en sentido horario) desde${\displaystyle 1}$a${\displaystyle {\sqrt {8n}}}$y vértice${\displaystyle i}$se corresponde con el vértice${\displaystyle {\sqrt {8n}}-i+1}$Entonces, estos pares coincidentes pueden conectarse mediante caminos disjuntos en vértices dentro del disco, mediante una forma del teorema de Menger para grafos planares. Sin embargo, la longitud total de estos caminos necesariamente excedería${\displaystyle n}$, una contradicción. Con un trabajo adicional, demuestran mediante un método similar que existe un separador de ciclos simple de tamaño como máximo${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$. ^{[ 7 ]}

Djidjev y Venkatesan (1997) mejoraron aún más el factor constante en el teorema del separador de ciclos simple para${\displaystyle 1.97{\sqrt {n}}}$Su método también puede encontrar separadores de ciclos simples para grafos con pesos de vértice no negativos, con un tamaño de separador como máximo${\displaystyle 2{\sqrt {n}}}$y pueden generar separadores de menor tamaño a costa de una partición más desigual del grafo. ^{[ 8 ]} En grafos planares biconexos que no son maximales, existen separadores de ciclos simples con un tamaño proporcional a la norma euclidiana del vector de longitudes de caras que se pueden encontrar en tiempo casi lineal. ^{[ 9 ]}

Según el teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston , cualquier grafo planar puede representarse mediante un empaquetamiento de discos circulares en el plano con interiores disjuntos, de tal manera que dos vértices del grafo son adyacentes si y solo si el par de discos correspondiente son mutuamente tangentes. Como muestran Miller et al. (1997) , para dicho empaquetamiento, existe un círculo que tiene como máximo${\displaystyle 3n/4}$discos que lo tocan o están dentro de él, como máximo${\displaystyle 3n/4}$discos que lo tocan o están fuera de él, y que lo cruzan${\displaystyle O({\sqrt {n}})}$discos. ^{[ 10 ]}

Para demostrar esto, Miller et al. utilizan la proyección estereográfica para mapear el empaquetamiento sobre la superficie de una esfera unitaria en tres dimensiones. Al elegir cuidadosamente la proyección, el centro de la esfera puede convertirse en un punto central de los centros de los discos en su superficie, de modo que cualquier plano que pase por el centro de la esfera la divide en dos semiespacios que contienen o cruzan como máximo${\displaystyle 3n/4}$de los discos. Si se elige un plano que pasa por el centro de forma uniforme y aleatoria, un disco será cruzado con una probabilidad proporcional a su radio. Por lo tanto, el número esperado de discos que son cruzados es proporcional a la suma de los radios de los discos. Sin embargo, la suma de los cuadrados de los radios es proporcional al área total de los discos, que es como máximo el área superficial total de la esfera unitaria, una constante. Un argumento que involucra la desigualdad de Jensen muestra que, cuando la suma de los cuadrados de los${\displaystyle n}$Los números reales no negativos están acotados por una constante, la suma de los números mismos es${\displaystyle O({\sqrt {n}})}$Por lo tanto, el número esperado de discos atravesados ​​por un plano aleatorio es${\displaystyle O({\sqrt {n}})}$y existe un plano que cruza como máximo esa cantidad de discos. Este plano interseca la esfera en un círculo máximo , que se proyecta de nuevo hacia abajo en un círculo en el plano con las propiedades deseadas.${\displaystyle O({\sqrt {n}})}$Los discos atravesados ​​por este círculo corresponden a los vértices de un separador de grafo planar que separa los vértices cuyos discos están dentro del círculo de los vértices cuyos discos están fuera del círculo, con como máximo${\displaystyle 3n/4}$vértices en cada uno de estos dos subconjuntos. ^{[ 11 ]}

Este método conduce a un algoritmo aleatorio que encuentra dicho separador en tiempo lineal , ^{[ 10 ]} y un algoritmo determinista menos práctico con el mismo límite de tiempo lineal. ^{[ 12 ]} Al analizar cuidadosamente este algoritmo utilizando límites conocidos en la densidad de empaquetamiento de empaquetamientos circulares , se puede demostrar que encuentra separadores de tamaño como máximo ^{[ 13 ]}$${\displaystyle {\sqrt {\frac {2\pi }{\sqrt {3}}}}\left({\frac {1+{\sqrt {3}}}{2{\sqrt {2}}}}+o(1)\right){\sqrt {n}}\approx 1.84{\sqrt {n}}.}$$ Aunque este límite mejorado para el tamaño del separador conlleva una partición más desigual del grafo, Spielman y Teng (1996) argumentan que proporciona un factor constante mejorado en los límites de tiempo para la disección anidada en comparación con los separadores de Alon, Seymour y Thomas (1990) . El tamaño de los separadores que produce se puede mejorar aún más, en la práctica, utilizando una distribución no uniforme para los planos de corte aleatorios. ^{[ 14 ]}

La proyección estereográfica en el argumento de Miller et al. puede evitarse considerando el círculo más pequeño que contiene una fracción constante de los centros de los discos y luego expandiéndolo por una constante elegida uniformemente en el rango${\displaystyle [1,2]}$Como en Miller et al., los discos que intersecan el círculo expandido forman un separador válido y, en teoría, el separador tiene el tamaño correcto. Las constantes resultantes son algo peores. ^{[ 15 ]}

Los métodos de agrupamiento espectral , en los que los vértices de un grafo se agrupan por las coordenadas de los autovectores de matrices derivadas del grafo, se han utilizado durante mucho tiempo como heurística para problemas de partición de grafos no planares. ^{[ 16 ]} Como muestran Spielman y Teng (2007) , el agrupamiento espectral también puede utilizarse para derivar una demostración alternativa de una forma debilitada del teorema del separador planar que se aplica a grafos planares con grado acotado. En su método, los vértices de un grafo planar dado se ordenan por las segundas coordenadas de los autovectores de la matriz laplaciana del grafo, y este orden ordenado se particiona en el punto que minimiza la razón entre el número de aristas cortadas por la partición y el número de vértices en el lado más pequeño de la partición. Como muestran, todo grafo planar de grado acotado tiene una partición de este tipo en la que la razón es${\displaystyle O(1/{\sqrt {n}})}$Aunque esta partición puede no estar equilibrada, repetir la partición dentro del mayor de los dos lados y tomar la unión de los cortes formados en cada repetición eventualmente conducirá a una partición equilibrada con${\displaystyle O({\sqrt {n}})}$bordes. Los extremos de estos bordes forman un separador de tamaño${\displaystyle O({\sqrt {n}})}$. ^{[ 17 ]}

Una variación del teorema del separador planar involucra separadores de aristas , pequeños conjuntos de aristas que forman un corte entre dos subconjuntos.${\displaystyle A}$y${\displaystyle B}$de los vértices del grafo. Los dos conjuntos${\displaystyle A}$y${\displaystyle B}$cada uno debe tener un tamaño como máximo una fracción constante del número${\displaystyle n}$de vértices del grafo (convencionalmente, ambos conjuntos tienen un tamaño máximo de )${\displaystyle 2n/3}$), y cada vértice del grafo pertenece exactamente a uno de${\displaystyle A}$y${\displaystyle B}$. El separador consta de los bordes que tienen un extremo en${\displaystyle A}$y un punto final en${\displaystyle B}$. Los límites del tamaño de un separador de aristas involucran el grado de los vértices, así como el número de vértices en el grafo: los grafos planares en los que un vértice tiene grado${\displaystyle n-1}$, incluyendo los grafos de rueda y los grafos estrella , no tienen separador de aristas con un número sublineal de aristas, porque cualquier separador de aristas tendría que incluir todas las aristas que conectan el vértice de alto grado con los vértices del otro lado del corte. Sin embargo, todo grafo planar con grado máximo${\displaystyle \Delta }$tiene un separador de bordes de tamaño${\displaystyle O({\sqrt {\Delta n}})}$. ^{[ 18 ]}

Un separador de ciclos simple en el grafo dual de un grafo planar forma un separador de aristas en el grafo original. ^{[ 19 ]} La aplicación del teorema del separador de ciclos simple de Gazit y Miller (1990) al grafo dual de un grafo planar dado fortalece el${\displaystyle O({\sqrt {\Delta n}})}$acotar el tamaño de un separador de aristas demostrando que todo grafo planar tiene un separador de aristas cuyo tamaño es proporcional a la norma euclidiana de su vector de grados de vértice.

Papadimitriou y Sideri (1996) describen un algoritmo de tiempo polinomial para encontrar el separador de aristas más pequeño que particiona un grafo.${\displaystyle G}$en dos subgrafos de igual tamaño, cuando${\displaystyle G}$es un subgrafo inducido de un grafo de cuadrícula sin agujeros o con un número constante de agujeros. Sin embargo, conjeturan que el problema es NP-completo para grafos planares arbitrarios, y demuestran que la complejidad del problema es la misma para grafos de cuadrícula con un número arbitrario de agujeros que para grafos planares arbitrarios.

Las descomposiciones de separadores pueden ser útiles para diseñar algoritmos eficientes de divide y vencerás para resolver problemas en grafos planares. Por ejemplo, un problema que se puede resolver de esta manera es encontrar el ciclo más corto en un digrafo planar ponderado. Esto se puede resolver siguiendo los siguientes pasos:

• Particionar el grafo dado${\displaystyle G}$en tres subconjuntos${\displaystyle S}$,${\displaystyle A}$,${\displaystyle B}$según el teorema del separador planar
• Buscar recursivamente los ciclos más cortos en${\displaystyle A}$y${\displaystyle B}$
• Utilice el algoritmo de Dijkstra para encontrar, para cada vértice${\displaystyle s}$en${\displaystyle S}$, el ciclo más corto a través de${\displaystyle s}$en${\displaystyle G}$.
• Devuelve el ciclo más corto de los encontrados en los pasos anteriores.

El tiempo para las dos llamadas recursivas a${\displaystyle A}$y${\displaystyle B}$En este algoritmo, está dominado por el tiempo para realizar la${\displaystyle O({\sqrt {n}})}$llamadas al algoritmo de Dijkstra, por lo que este algoritmo encuentra el ciclo más corto en${\displaystyle O(n^{3/2}\log n)}$tiempo.

Un algoritmo más rápido para el mismo problema del ciclo más corto, que se ejecuta en tiempo${\displaystyle O(n\log ^{3}n)}$, fue dado por Wulff-Nilsen (2009) . Su algoritmo utiliza la misma estructura de divide y vencerás basada en separadores, pero utiliza separadores de ciclo simples en lugar de separadores arbitrarios, de modo que los vértices de${\displaystyle S}$pertenecen a una sola cara de los gráficos dentro y fuera del separador de ciclos. Luego reemplaza el${\displaystyle O({\sqrt {n}})}$ llamadas separadas al algoritmo de Dijkstra con algoritmos más sofisticados para encontrar caminos más cortos desde todos los vértices en una sola cara de un grafo planar y para combinar las distancias de los dos subgrafos. Para grafos planares ponderados pero no dirigidos, el ciclo más corto es equivalente al corte mínimo en el grafo dual y se puede encontrar en${\displaystyle O(n\log \log n)}$tiempo, ^{[ 27 ]} y el ciclo más corto en un grafo planar no dirigido no ponderado (su circunferencia ) se puede encontrar en tiempo${\displaystyle O(n)}$. ^{[ 28 ]} (Sin embargo, el algoritmo más rápido para grafos no ponderados no se basa en el teorema del separador.)

Frederickson propuso otro algoritmo más rápido para caminos más cortos desde un único origen mediante la implementación del teorema del separador en grafos planares. ^{[ 29 ]} Esta es una mejora del algoritmo de Dijkstra con búsqueda iterativa en un subconjunto cuidadosamente seleccionado de los vértices. Esta versión toma${\displaystyle O(n{\sqrt {\log n}})}$tiempo en un${\displaystyle n}$-grafo de vértices. Los separadores se utilizan para encontrar una división de un grafo, es decir, una partición del conjunto de aristas en dos o más subconjuntos, llamados regiones. Se dice que un nodo está contenido en una región si alguna arista de la región es incidente al nodo. Un nodo contenido en más de una región se llama nodo frontera de las regiones que lo contienen. El método utiliza la noción de un${\displaystyle r}$-división de un${\displaystyle n}$-grafo de nodos que es una división de grafo en${\displaystyle O(n/r)}$regiones, cada una de las cuales contiene${\displaystyle O(r)}$nodos que incluyen${\displaystyle O({\sqrt {r}})}$nodos de frontera. Frederickson demostró que un${\displaystyle r}$-la división se puede encontrar en${\displaystyle O(n\log n)}$tiempo mediante la aplicación recursiva del teorema del separador.

El esquema de su algoritmo para resolver el problema es el siguiente.

1. Fase de preprocesamiento: Dividir el grafo en subconjuntos de vértices cuidadosamente seleccionados y determinar los caminos más cortos entre todos los pares de vértices en estos subconjuntos, donde los vértices intermedios en este camino no se encuentran en el subconjunto. Esta fase requiere un grafo planar.${\displaystyle G_{0}}$ser transformado en${\displaystyle G}$sin que ningún vértice tenga un grado mayor que tres. A partir de un corolario de la fórmula de Euler , el número de vértices en el grafo resultante será${\displaystyle n\leq 6n_{0}-12}$, dónde${\displaystyle n_{0}}$es el número de vértices en${\displaystyle G_{0}}$Esta fase también garantiza las siguientes propiedades de un material adecuado.${\displaystyle r}$-división. Una adecuada${\displaystyle r}$-la división de un grafo planar es una${\displaystyle r}$-división tal que,
   • cada vértice del límite está contenido en como máximo tres regiones, y
   • Cualquier región que no esté conectada consta de componentes conectadas, todas las cuales comparten vértices de frontera con exactamente el mismo conjunto de una o dos regiones conectadas.
2. Fase de búsqueda:
   • Objetivo principal: Encontrar las distancias más cortas desde la fuente a cada vértice en el subconjunto. Cuando un vértice${\displaystyle v}$en el subconjunto está cerrado, la distancia tentativa${\displaystyle d(w)}$Debe actualizarse para todos los vértices.${\displaystyle w}$en el subconjunto tal que existe un camino desde${\displaystyle v}$a${\displaystyle w}$.
   • Remate: Determinar las distancias más cortas a cada vértice restante.

Henzinger y otros extendieron el trabajo de Frederickson.${\displaystyle r}$-técnica de división para el algoritmo de ruta más corta de origen único en grafos planares para longitudes de aristas no negativas y propuso un algoritmo de tiempo lineal . ^{[ 30 ]} Su método generaliza la noción de divisiones de grafos de Frederickson de tal manera que ahora un${\displaystyle (r,s)}$-división de un${\displaystyle n}$-el gráfico de nodos es una división en${\displaystyle O(n/r)}$regiones, cada una de las cuales contiene${\displaystyle r^{O(1)}}$nodos, cada uno con como máximo${\displaystyle s}$nodos límite. Si un${\displaystyle (r,s)}$La división se divide repetidamente en regiones más pequeñas, lo que se denomina división recursiva. Este algoritmo utiliza aproximadamente${\displaystyle \log ^{*}n}$niveles de divisiones, donde${\displaystyle \log ^{*}}$denota la función logaritmo iterada . La división recursiva está representada por un árbol con raíz cuyas hojas están etiquetadas por aristas distintas de${\displaystyle G}$. La raíz del árbol representa la región que comprende todos los${\displaystyle G}$Los hijos de la raíz representan las subregiones en las que se divide esa región, y así sucesivamente. Cada hoja (región atómica) representa una región que contiene exactamente una arista.

La disección anidada es una variación de la eliminación gaussiana basada en el método de divide y vencerás con separadores para resolver sistemas simétricos dispersos de ecuaciones lineales con una estructura gráfica planar, como los que surgen del método de elementos finitos . Implica encontrar un separador para el grafo que describe el sistema de ecuaciones, eliminar recursivamente las variables en los dos subproblemas separados entre sí por el separador y luego eliminar las variables en el separador. ^{[ 31 ]} El relleno de este método (el número de coeficientes no nulos de la descomposición de Cholesky resultante de la matriz) es${\displaystyle O(n\log n)}$, ^{[ 32 ]} permitiendo que este método sea competitivo con los métodos iterativos para los mismos problemas. ^{[ 31 ]}

Klein, Mozes y Weimann ^{[ 33 ]} dieron una${\displaystyle O(n\log ^{2}n)}$-algoritmo de tiempo y espacio lineal para encontrar las distancias de camino más cortas desde un vértice de origen${\displaystyle s}$a todos los demás vértices para un grafo planar dirigido con longitudes de arco positivas y negativas que no contiene ciclos negativos. Su algoritmo utiliza separadores de grafos planares para encontrar una curva de Jordan.${\displaystyle C}$que pasa por${\displaystyle O({\sqrt {n}})}$nodos (y ningún arco) de tal manera que entre${\displaystyle n/3}$y${\displaystyle 2n/3}$Los nodos están encerrados por${\displaystyle C}$. Nodos a través de los cuales${\displaystyle C}$Los pasos son nodos límite . El gráfico original${\displaystyle G}$se divide en dos subgrafos${\displaystyle G_{0}}$y${\displaystyle G_{1}}$cortando la incrustación planar a lo largo${\displaystyle C}$y duplicando los nodos límite. Los nodos límite en cada grafo${\displaystyle G_{i}}$yacer en el límite de una sola cara${\displaystyle F_{i}}$.

A continuación se ofrece una descripción general de su enfoque.

• Llamada recursiva: La primera etapa calcula recursivamente las distancias desde${\displaystyle r}$dentro de cada gráfico${\displaystyle G_{i}}$.
• Distancias límite intraparte: Para cada gráfico${\displaystyle G_{i}}$calcular todas las distancias en${\displaystyle G_{i}}$entre nodos límite. Esto toma${\displaystyle O(n\log n)}$tiempo.
• Distancias límite entre partes de una sola fuente: Un camino más corto en${\displaystyle G}$pasa de un lado a otro entre${\displaystyle G_{0}}$y${\displaystyle G_{1}}$para calcular las distancias en${\displaystyle G}$de${\displaystyle r}$a todos los nodos límite. Las iteraciones alternas utilizan todas las distancias límite en${\displaystyle G_{0}}$y${\displaystyle G_{1}}$El número de iteraciones es${\displaystyle O({\sqrt {n}})}$y el tiempo total para esta etapa es${\displaystyle O(n\alpha (n))}$dónde${\displaystyle \alpha (n)}$es la función inversa de Ackermann .
• Distancias entre partes de una sola fuente: Las distancias calculadas en las etapas anteriores se utilizan, junto con un cálculo de Dijkstra dentro de una versión modificada de cada G _i  , para calcular las distancias en${\displaystyle G}$de${\displaystyle r}$a todos los nodos. Esta etapa toma${\displaystyle O(n\log n)}$tiempo.
• Recalcular las distancias de origen único: Las distancias de${\displaystyle r}$en${\displaystyle G}$se transforman en longitudes no negativas y, de nuevo, se utiliza el algoritmo de Dijkstra para calcular distancias desde${\displaystyle s}$Esta etapa requiere${\displaystyle O(n\log n)}$tiempo.

Una parte importante de este algoritmo es el uso de funciones de precio y longitudes reducidas. Para un grafo dirigido${\displaystyle G}$con longitudes de arco${\displaystyle \ell (uv)}$, una función de precio es una función${\displaystyle \varphi }$desde los nodos de${\displaystyle G}$a los números reales . Para un arco${\displaystyle uv}$, la longitud reducida con respecto a${\displaystyle \varphi }$es${\displaystyle \ell _{\varphi }(uv)=\ell (uv)+\varphi (u)-\varphi (v)}$. Una función de precio factible es una función de precio que induce longitudes reducidas no negativas en todos los arcos de${\displaystyle G}$Resulta útil para transformar un problema de camino más corto que involucra longitudes positivas y negativas en uno que involucra solo longitudes no negativas, el cual luego puede resolverse utilizando el algoritmo de Dijkstra.

El paradigma de divide y vencerás basado en separadores también se ha utilizado para diseñar estructuras de datos para algoritmos de grafos dinámicos ^{[ 34 ]} y localización de puntos , ^{[ 35 ]} algoritmos para triangulación de polígonos , ^{[ 20 ]} caminos más cortos , ^{[ 36 ]} y la construcción de grafos de vecinos más cercanos , ^{[ 37 ]} y algoritmos de aproximación para el conjunto independiente máximo de un grafo planar. ^{[ 35 ]}

Mediante el uso de programación dinámica en una descomposición en árbol o descomposición en ramas de un grafo planar, muchos problemas de optimización NP-difíciles pueden resolverse en tiempo exponencial en${\displaystyle {\sqrt {n}}}$o${\displaystyle {\sqrt {n}}\log n}$Por ejemplo, se conocen cotas de esta forma para encontrar conjuntos independientes máximos , árboles de Steiner y ciclos hamiltonianos , y para resolver el problema del viajante en grafos planares. ^{[ 38 ]} Métodos similares que involucran teoremas de separación para grafos geométricos pueden usarse para resolver el problema del viajante euclidiano y problemas de construcción de árboles de Steiner en cotas de tiempo de la misma forma. ^{[ 39 ]}

Para problemas parametrizados que admiten una kernelización que preserva la planaridad y reduce el grafo de entrada a un kernel de tamaño lineal en el parámetro de entrada, este enfoque puede utilizarse para diseñar algoritmos tratables de parámetros fijos cuyo tiempo de ejecución depende polinómicamente del tamaño del grafo de entrada y exponencialmente de${\displaystyle {\sqrt {k}}}$, dónde${\displaystyle k}$es el parámetro del algoritmo. Por ejemplo, se conocen límites de tiempo de esta forma para encontrar cubiertas de vértices y conjuntos dominantes de tamaño${\displaystyle k}$. ^{[ 40 ]}

Lipton y Tarjan (1980) observaron que el teorema del separador puede usarse para obtener esquemas de aproximación de tiempo polinomial para problemas de optimización NP-difíciles en grafos planares, como encontrar el conjunto independiente máximo . Específicamente, al truncar una jerarquía de separadores en un nivel apropiado, se puede encontrar un separador de tamaño${\displaystyle O(n/{\sqrt {\log n}})}$La eliminación de la cual divide el grafo en subgrafos de tamaño como máximo${\displaystyle c\log n}$, para cualquier constante${\displaystyle c}$Por el teorema de los cuatro colores , existe un conjunto independiente de tamaño al menos${\displaystyle n/4}$, por lo que los nodos eliminados forman una fracción insignificante del conjunto independiente máximo, y los conjuntos independientes máximos en los subgrafos restantes se pueden encontrar de forma independiente en un tiempo exponencial en su tamaño. Al combinar este enfoque con métodos posteriores de tiempo lineal para la construcción de jerarquías de separadores ^{[ 20 ]} y con búsqueda en tablas para compartir el cálculo de conjuntos independientes entre subgrafos isomorfos , se puede hacer que construya conjuntos independientes de tamaño dentro de un factor de${\displaystyle 1-1/{\sqrt {\log n}}}$de óptimo, en tiempo lineal. Sin embargo, para razones de aproximación aún más cercanas a uno que este factor, un enfoque posterior de Baker (1994) (basado en la descomposición en árbol pero no en separadores planares) proporciona mejores compensaciones entre tiempo y calidad de aproximación.

Esquemas de aproximación similares basados ​​en separadores también se han utilizado para aproximar otros problemas difíciles como la cobertura de vértices . ^{[ 41 ]} Arora et al. (1998) utilizan separadores de una manera diferente para aproximar el problema del viajante de comercio para la métrica de camino más corto en grafos planares ponderados; su algoritmo utiliza programación dinámica para encontrar el recorrido más corto que, en cada nivel de una jerarquía de separadores, cruza el separador un número limitado de veces, y muestran que a medida que aumenta el límite de cruce, los recorridos construidos de esta manera tienen longitudes que se aproximan al recorrido óptimo.

Los separadores se han utilizado como parte de algoritmos de compresión de datos para representar grafos planares y otros grafos separables utilizando un pequeño número de bits. El principio básico de estos algoritmos es elegir un número${\displaystyle k}$y subdividir repetidamente el grafo planar dado utilizando separadores en${\displaystyle O(n/k)}$subgrafos de tamaño como máximo${\displaystyle k}$, con${\displaystyle O(n/{\sqrt {k}})}$vértices en los separadores. Con una elección apropiada de${\displaystyle k}$(como máximo proporcional al logaritmo de${\displaystyle n}$) el número de no isomorfos${\displaystyle k}$El número de subgrafos planares de vértices es significativamente menor que el número de subgrafos en la descomposición, por lo que el grafo se puede comprimir construyendo una tabla de todos los posibles subgrafos no isomorfos y representando cada subgrafo en la descomposición del separador por su índice en la tabla. El resto del grafo, formado por los vértices del separador, se puede representar explícitamente o utilizando una versión recursiva de la misma estructura de datos. Usando este método, los grafos planares y muchas familias de grafos más restringidas se pueden codificar usando una cantidad de bits que es óptima desde el punto de vista de la teoría de la información : si hay${\displaystyle P_{n}}$${\displaystyle n}$-grafos de vértices en la familia de grafos a representar, entonces un grafo individual en la familia puede representarse usando solo${\displaystyle (1+o(1))\log _{2}P_{n}}$bits. ^{[ 42 ]} También es posible construir representaciones de este tipo en las que se puede probar la adyacencia entre vértices, determinar el grado de un vértice y listar los vecinos de los vértices en tiempo constante por consulta, aumentando la tabla de subgrafos con información tabular adicional que represente las respuestas a las consultas. ^{[ 43 ]}

Un gráfico universal para una familia${\displaystyle {\mathcal {F}}}$de grafos es un grafo que contiene cada miembro de${\displaystyle {\mathcal {F}}}$como subgrafos. Se pueden usar separadores para mostrar que el${\displaystyle n}$Los grafos planares de vértices tienen grafos universales con${\displaystyle n}$vértices y${\displaystyle O(n^{3/2})}$bordes. ^{[ 44 ]}

La construcción implica una forma reforzada del teorema del separador en la que el tamaño de los tres subconjuntos de vértices en el separador no depende de la estructura del grafo: existe un número${\displaystyle c}$cuya magnitud es como máximo un tiempo constante${\displaystyle {\sqrt {n}}}$, de tal manera que los vértices de cada${\displaystyle n}$-Un grafo planar de vértices se puede separar en subconjuntos.${\displaystyle A}$,${\displaystyle S}$, y${\displaystyle B}$, sin bordes de${\displaystyle A}$a${\displaystyle B}$, con${\displaystyle |S|=c}$y con${\displaystyle |A|=|B|=(n-c)/2}$Esto se puede demostrar utilizando repetidamente la forma habitual del teorema del separador para particionar el grafo hasta que todos los componentes de la partición se puedan organizar en dos subconjuntos de menos de${\displaystyle n/2}$vértices, y luego mover vértices de estos subconjuntos al separador según sea necesario hasta que tenga el tamaño dado.

Una vez que se demuestra un teorema separador de este tipo, se puede utilizar para producir una jerarquía separadora para${\displaystyle n}$-grafos planares de vértices que nuevamente no dependen de la estructura del grafo: la descomposición en árbol formada a partir de esta jerarquía tiene ancho${\displaystyle O({\sqrt {n}})}$y puede utilizarse para cualquier grafo planar. El conjunto de todos los pares de vértices en esta descomposición en árbol que pertenecen a un nodo común de la descomposición en árbol forma un grafo trivialmente perfecto con${\displaystyle O(n^{3/2})}$vértices que contienen cada${\displaystyle n}$-grafo planar de vértices como subgrafo. Una construcción similar muestra que los grafos planares de grado acotado tienen grafos universales con${\displaystyle O(n\log n)}$bordes, donde la constante oculta en la notación O depende del límite de grado. Cualquier grafo universal para grafos planares (o incluso para árboles de grado no acotado) debe tener${\displaystyle \Omega (n\log n)}$bordes. ^{[ 44 ]}

Esperet, Joret y Morin (2020) anunciaron que el${\displaystyle O(n^{3/2})}$La construcción que utiliza separadores puede mejorarse, para${\displaystyle n^{1+o(1)}}$.