Teorema del separador planar

Cualquier gráfico plano se puede subdividir eliminando algunos vértices.

En teoría de grafos , el teorema del separador planar es una forma de desigualdad isoperimétrica para grafos planares , que establece que cualquier grafo planar se puede dividir en partes más pequeñas eliminando una pequeña cantidad de vértices . Específicamente, la eliminación de ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ vértices de un grafo de n -vértices (donde O invoca la notación O grande ) puede dividir el grafo en subgrafos disjuntos, cada uno de los cuales tiene como máximo ⁠ ⁠ ${\displaystyle 2n/3}$ vértices.

Una forma más débil del teorema del separador con vértices en ${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$ el separador en lugar de ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ fue demostrada originalmente por Ungar (1951), y la forma con el límite asintótico estricto en el tamaño del separador fue demostrada por primera vez por Lipton y Tarjan (1979). Desde su trabajo, el teorema del separador ha sido refutado de varias maneras diferentes, la constante en el término ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ del teorema ha sido mejorada y se ha extendido a ciertas clases de grafos no planos.

La aplicación repetida del teorema del separador produce una jerarquía de separadores que puede adoptar la forma de una descomposición en árbol o de una descomposición en ramas del gráfico. Las jerarquías de separadores se pueden utilizar para diseñar algoritmos eficientes de divide y vencerás para gráficos planares, y la programación dinámica en estas jerarquías se puede utilizar para diseñar algoritmos manejables con parámetros fijos y tiempo exponencial para resolver problemas de optimización NP-hard en estos gráficos. Las jerarquías de separadores también se pueden utilizar en la disección anidada , una variante eficiente de la eliminación gaussiana para resolver sistemas dispersos de ecuaciones lineales que surgen de métodos de elementos finitos .

Además de los grafos planares, los teoremas del separador se han aplicado a otras clases de grafos, incluidos los grafos que excluyen un menor fijo , los grafos del vecino más próximo y las mallas de elementos finitos . La existencia de un teorema del separador para una clase de grafos se puede formalizar y cuantificar mediante los conceptos de ancho de árbol y expansión polinómica .

Enunciado del teorema

Como se suele afirmar, el teorema del separador establece que, en cualquier grafo plano de -vértice , existe una partición de los vértices de en tres conjuntos , , y , tales que cada uno de y tiene como máximo vértices, tiene vértices, y no hay aristas con un extremo en y un extremo en . No se requiere que o formen subgrafos conexos de . se denomina separador para esta partición. ${\displaystyle n}$ ${\displaystyle G=(V,E)}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2n/3}$ ${\displaystyle S}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle G}$ ${\displaystyle S}$

Una formulación equivalente es que las aristas de cualquier grafo planar de -vértice pueden subdividirse en dos subgrafos disjuntos en aristas y de tal manera que ambos subgrafos tengan al menos vértices y de tal manera que la intersección de los conjuntos de vértices de los dos subgrafos tenga vértices en ella. Tal partición se conoce como separación . ^[1] Si se da una separación, entonces la intersección de los conjuntos de vértices forma un separador, y los vértices que pertenecen a un subgrafo pero no al otro forman subconjuntos separados, cada uno con como máximo vértices. En la otra dirección, si se da una partición en tres conjuntos , , y que cumplen las condiciones del teorema del separador planar, entonces se puede formar una separación en la que las aristas con un punto final en pertenecen a , las aristas con un punto final en pertenecen a , y las aristas restantes (con ambos puntos finales en ) se particionan arbitrariamente. ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle n/3}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle 2n/3}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G_{1}}$ ${\displaystyle B}$ ${\displaystyle G_{2}}$ ${\displaystyle S}$

La constante en el enunciado del teorema del separador es arbitraria y puede ser reemplazada por cualquier otro número en el intervalo abierto sin cambiar la forma del teorema: una partición en subconjuntos más iguales puede obtenerse a partir de una partición menos par dividiendo repetidamente los conjuntos más grandes en la partición desigual y reagrupando los componentes conectados resultantes. ^[2] ${\displaystyle 2/3}$ ${\displaystyle (1/2,1)}$

Ejemplo

Un separador plano para un gráfico de cuadrícula

Consideremos un gráfico de cuadrícula con filas y columnas; el número de vértices es igual a . Por ejemplo, en la ilustración, , , y . Si es impar, hay una sola fila central y, de lo contrario, hay dos filas igualmente cercanas al centro; de manera similar, si es impar, hay una sola columna central y, de lo contrario, hay dos columnas igualmente cercanas al centro. Elegir cualquiera de estas filas o columnas centrales y eliminar del gráfico, divide el gráfico en dos subgrafos conectados más pequeños y , cada uno de los cuales tiene como máximo vértices. Si (como en la ilustración), entonces elegir una columna central dará un separador con vértices y, de manera similar, si entonces elegir una fila central dará un separador con como máximo vértices. Por lo tanto, cada gráfico de cuadrícula tiene un separador de tamaño como máximo , cuya eliminación lo divide en dos componentes conectados, cada uno de tamaño como máximo . ^[3] ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle rc}$ ${\displaystyle r=5}$ ${\displaystyle c=8}$ ${\displaystyle n=rc=40}$ ${\displaystyle r}$ ${\displaystyle c}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n/2}$ ${\displaystyle r\leq c}$ ${\displaystyle S}$ ${\displaystyle r\leq {\sqrt {n}}}$ ${\displaystyle c\leq r}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n/2}$

El teorema del separador planar establece que se puede construir una partición similar en cualquier grafo planar. El caso de grafos planares arbitrarios difiere del caso de grafos de cuadrícula en que el separador tiene un tamaño pero puede ser mayor que , el límite del tamaño de los dos subconjuntos y (en las versiones más comunes del teorema) es en lugar de , y los dos subconjuntos y no necesitan formar subgrafos conexos. ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2n/3}$ ${\displaystyle n/2}$ ${\displaystyle A}$ ${\displaystyle B}$

Construcciones

Capas que priorizan la amplitud

Lipton y Tarjan (1979) aumentan el grafo planar dado con aristas adicionales, si es necesario, de modo que se vuelve planar máximo (cada cara en una incrustación planar es un triángulo). Luego realizan una búsqueda en amplitud , con raíz en un vértice arbitrario , y dividen los vértices en niveles por su distancia desde . Si es el nivel mediano (el nivel tal que los números de vértices en los niveles superior e inferior son ambos como máximo ), entonces debe haber niveles y que son pasos arriba y abajo respectivamente y que contienen vértices, respectivamente, porque de lo contrario habría más de vértices en los niveles cerca de . Muestran que debe haber un separador formado por la unión de y , los puntos finales de una arista de que no pertenece al árbol de búsqueda en amplitud y que se encuentra entre los dos niveles, y los vértices en los dos caminos del árbol de búsqueda en amplitud desde los puntos finales de de regreso al nivel . El tamaño del separador construido de esta manera es como máximo . Los vértices del separador y los dos subgrafos disjuntos se pueden encontrar en tiempo lineal . ^[4] ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle l_{1}}$ ${\displaystyle n/2}$ ${\displaystyle l_{0}}$ ${\displaystyle l_{2}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle l_{1}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle n}$ ${\displaystyle l_{1}}$ ${\displaystyle S}$ ${\displaystyle l_{0}}$ ${\displaystyle l_{2}}$ ${\displaystyle e}$ ${\displaystyle G}$ ${\displaystyle e}$ ${\displaystyle l_{0}}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {8n}}\approx 2.83{\sqrt {n}}}$

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

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

Separadores de ciclo simple

Para un grafo que ya es planar maximalista es posible mostrar una construcción más fuerte de un separador de ciclo 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 vértices. Miller (1986) demuestra esto (con un tamaño de separador de ) utilizando la técnica de 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] ${\displaystyle 2n/3}$ ${\displaystyle {\sqrt {8n}}}$

Alon, Seymour y Thomas (1994) prueban la existencia de separadores de ciclos simples de manera más directa: sea un ciclo de como máximo vértices, con como máximo vértices fuera de , que forme una partición lo más uniforme posible de interior y exterior. Muestran que estas suposiciones obligan a ser un separador. De lo contrario, las distancias dentro deben ser iguales a las distancias en el disco encerrado por (un camino más corto a través del interior del disco formaría parte del límite de un mejor ciclo). Además, debe tener longitud exactamente , 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 están numerados (en el sentido de las agujas del reloj) de a , y el vértice se empareja con el vértice , entonces estos pares emparejados pueden conectarse mediante caminos disjuntos entre vértices dentro del disco, por una forma del teorema de Menger para grafos planares. Sin embargo, la longitud total de estos caminos necesariamente excedería , una contradicción. Con algo de trabajo adicional, demuestran mediante un método similar que existe un separador de ciclo simple de tamaño como máximo . ^[7] ${\displaystyle C}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle 2n/3}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle C}$ ${\displaystyle 1}$ ${\displaystyle {\sqrt {8n}}}$ ${\displaystyle i}$ ${\displaystyle {\sqrt {8n}}-i+1}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {9n/2}}\approx 2.12{\sqrt {n}}}$

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

Separadores circulares

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

Para demostrarlo, Miller et al. utilizan la proyección estereográfica para representar el empaquetamiento sobre la superficie de una esfera unitaria en tres dimensiones. Al elegir la proyección con cuidado, 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 divida en dos semiespacios que contengan o crucen, cada uno, como máximo, los discos. Si se elige un plano que pase por el centro de manera uniforme y aleatoria, se cruzará un disco con una probabilidad proporcional a su radio. Por lo tanto, el número esperado de discos que se cruzan 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 de superficie 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 números reales no negativos está limitada por una constante, la suma de los números mismos es . Por lo tanto, el número esperado de discos atravesados ​​por un plano aleatorio es y existe un plano que cruza, como máximo, esa cantidad de discos. Este plano intersecta la esfera en un círculo máximo , que se proyecta hacia abajo hasta un círculo en el plano con las propiedades deseadas. Los discos atravesados ​​por este círculo corresponden a los vértices de un separador de grafos planares 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 un máximo de vértices en cada uno de estos dos subconjuntos. ^[11] ${\displaystyle 3n/4}$ ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle 3n/4}$

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 este algoritmo cuidadosamente 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] Aunque este límite de tamaño de separador mejorado se produce a expensas de una partición más desigual del gráfico, 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] $${\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}}.}$$

La proyección estereográfica en el argumento de Miller et al. se puede evitar 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 . Como en Miller et al., los discos que intersecan el círculo expandido forman un separador válido y, como era de esperar, el separador tiene el tamaño correcto. Las constantes resultantes son algo peores. ^[15] ${\displaystyle [1,2]}$

Partición espectral

Los métodos de agrupamiento espectral , en los que los vértices de un grafo se agrupan por las coordenadas de los vectores propios de las matrices derivadas del grafo, se han utilizado durante mucho tiempo como una heurística para problemas de partición de grafos para grafos no planares. ^[16] Como muestran Spielman y Teng (2007), el agrupamiento espectral también se puede utilizar para derivar una prueba alternativa para 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 vectores propios de la matriz laplaciana del grafo, y este orden ordenado se particiona en el punto que minimiza la relació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, cada grafo planar de grado acotado tiene una partición de este tipo en la que la relación es . Aunque esta partición puede no estar equilibrada, al repetir la partición dentro del lado más grande de los dos y tomar la unión de los cortes formados en cada repetición, eventualmente se obtendrá una partición equilibrada con aristas. Los puntos finales de estas aristas forman un separador de tamaño . ^[17] ${\displaystyle O(1/{\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Separadores de bordes

Una variación del teorema del separador planar implica separadores de aristas , pequeños conjuntos de aristas que forman un corte entre dos subconjuntos y de los vértices del grafo. Los dos conjuntos y deben tener cada uno un tamaño como máximo de una fracción constante del número de vértices del grafo (convencionalmente, ambos conjuntos tienen un tamaño como máximo ), y cada vértice del grafo pertenece exactamente a uno de y . El separador consta de las aristas que tienen un punto final en y un punto final en . Los límites en el 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 , incluyendo los grafos de rueda y los grafos de 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 a los vértices en el otro lado del corte. Sin embargo, cada grafo planar con grado máximo tiene un separador de aristas de tamaño . ^[18] ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle 2n/3}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n-1}$ ${\displaystyle \Delta }$ ${\displaystyle O({\sqrt {\Delta n}})}$

Un separador de ciclo simple en el gráfico dual de un gráfico planar forma un separador de aristas en el gráfico original. ^[19] La aplicación del teorema del separador de ciclo simple de Gazit y Miller (1990) al gráfico dual de un gráfico planar dado fortalece el límite para el tamaño de un separador de aristas al mostrar que cada gráfico planar tiene un separador de aristas cuyo tamaño es proporcional a la norma euclidiana de su vector de grados de vértice. ${\displaystyle O({\sqrt {\Delta n}})}$

Papadimitriou y Sideri (1996) describen un algoritmo de tiempo polinomial para encontrar el separador de aristas más pequeño que divide un grafo en dos subgrafos de igual tamaño, cuando 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 planos arbitrarios, y muestran que la complejidad del problema es la misma para grafos de cuadrícula con una cantidad arbitraria de agujeros que para grafos planos arbitrarios. ${\displaystyle G}$ ${\displaystyle G}$

Límites inferiores

Un poliedro formado al reemplazar cada una de las caras de un icosaedro por una malla de 100 triángulos, un ejemplo de la construcción del límite inferior de Djidjev (1982)

En un gráfico de cuadrícula, un conjunto de puntos puede encerrar un subconjunto de, como máximo, puntos de cuadrícula, donde el máximo se logra al organizarlos en una línea diagonal cerca de una esquina de la cuadrícula. Por lo tanto, para formar un separador que separe al menos de los puntos del resto de la cuadrícula, debe haber al menos . ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ ${\displaystyle S}$ ${\displaystyle s<{\sqrt {n}}}$ ${\displaystyle s(s-1)/2}$ ${\displaystyle S}$ ${\displaystyle n/3}$ ${\displaystyle s}$ ${\displaystyle {\sqrt {2n/3}}\approx 0.82{\sqrt {n}}}$

Existen grafos planares de -vértice (para valores arbitrariamente grandes de ) tales que, para cada separador que divide el grafo restante en subgrafos de como máximo vértices, tiene al menos . ^[2] La construcción implica aproximar una esfera por un poliedro convexo , reemplazar cada una de las caras del poliedro por una malla triangular y aplicar teoremas isoperimétricos para la superficie de la esfera. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle 2n/3}$ ${\displaystyle S}$ ${\displaystyle {\sqrt {4\pi n/{\sqrt {27}}}}\approx 1.56{\sqrt {n}}}$

Jerarquías de separadores

Los separadores pueden combinarse en una jerarquía de separadores de un grafo plano, una descomposición recursiva en grafos más pequeños. Una jerarquía de separadores puede representarse mediante un árbol binario en el que el nodo raíz representa el grafo dado en sí mismo, y los dos hijos de la raíz son las raíces de jerarquías de separadores construidas recursivamente para los subgrafos inducidos formados a partir de los dos subconjuntos y de un separador. ${\displaystyle A}$ ${\displaystyle B}$

Una jerarquía de separadores de este tipo forma la base para una descomposición en árbol del grafo dado, en la que el conjunto de vértices asociados con cada nodo del árbol es la unión de los separadores en el camino desde ese nodo hasta la raíz del árbol. Dado que los tamaños de los grafos disminuyen en un factor constante en cada nivel del árbol, los límites superiores de los tamaños de los separadores también disminuyen en un factor constante en cada nivel, por lo que los tamaños de los separadores en estos caminos se suman en una serie geométrica para . Es decir, un separador formado de esta manera tiene ancho , y se puede utilizar para mostrar que cada grafo plano tiene ancho de árbol . ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Construir una jerarquía de separadores directamente, recorriendo el árbol binario de arriba hacia abajo y aplicando un algoritmo de separador planar de tiempo lineal a cada uno de los subgrafos inducidos asociados con cada nodo del árbol binario, llevaría un tiempo total de 1000 años. Sin embargo, es posible construir una jerarquía de separadores completa en tiempo lineal, utilizando el enfoque de capas en amplitud de Lipton-Tarjan y utilizando estructuras de datos apropiadas para realizar cada paso de partición en tiempo sublineal. ^[20] ${\displaystyle O(n\log n)}$

Si se forma un tipo relacionado de jerarquía basado en separaciones en lugar de separadores, en el que los dos hijos del nodo raíz son raíces de jerarquías construidas recursivamente para los dos subgrafos y de una separación del grafo dado, entonces la estructura general forma una descomposición en rama en lugar de una descomposición en árbol. El ancho de cualquier separación en esta descomposición está, nuevamente, limitado por la suma de los tamaños de los separadores en una ruta desde cualquier nodo a la raíz de la jerarquía, por lo que cualquier descomposición en rama formada de esta manera tiene ancho y cualquier grafo planar tiene ancho de rama . Aunque muchos otros problemas relacionados de partición de grafos son NP-completos , incluso para grafos planares, es posible encontrar una descomposición en rama de ancho mínimo de un grafo planar en tiempo polinomial. ^[21] ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Aplicando los métodos de Alon, Seymour y Thomas (1994) más directamente en la construcción de descomposiciones de ramas, Fomin y Thilikos (2006a) muestran que cada grafo planar tiene un ancho de rama como máximo , con la misma constante que la del teorema del separador de ciclo simple de Alon et al. Dado que el ancho de árbol de cualquier grafo es como máximo el ancho de su rama, esto también muestra que los grafos planares tienen un ancho de árbol como máximo . ${\displaystyle 2.12{\sqrt {n}}}$ ${\displaystyle 3/2}$ ${\displaystyle 3.18{\sqrt {n}}}$

Otras clases de gráficos

Algunos gráficos dispersos no tienen separadores de tamaño sublineal: en un gráfico expansor , eliminar hasta una fracción constante de los vértices todavía deja solo un componente conectado. ^[22]

Posiblemente el teorema del separador más antiguo conocido es un resultado de Jordan (1869) que sostiene que cualquier árbol puede dividirse en subárboles de como máximo vértices cada uno mediante la eliminación de un único vértice. ^[10] En particular, el vértice que minimiza el tamaño máximo del componente tiene esta propiedad, ya que si no lo hiciera, su vecino en el único subárbol grande formaría una partición aún mejor. Al aplicar la misma técnica a una descomposición en árbol de un grafo arbitrario, es posible demostrar que cualquier grafo tiene un separador de tamaño como máximo igual a su ancho de árbol . ${\displaystyle n/2}$

Si un grafo no es plano, pero puede ser incrustado en una superficie de género , entonces tiene un separador con vértices. Gilbert, Hutchinson y Tarjan (1984) prueban esto usando un enfoque similar al de Lipton y Tarjan (1979). Agrupan los vértices del grafo en niveles de amplitud y encuentran dos niveles cuya eliminación deja como máximo un componente grande que consiste en un pequeño número de niveles. Este componente restante puede hacerse plano eliminando un número de caminos de amplitud proporcional al género, después de lo cual el método de Lipton-Tarjan puede aplicarse al grafo plano restante. El resultado se desprende de un equilibrio cuidadoso del tamaño de los dos niveles eliminados contra el número de niveles entre ellos. Si la incrustación del grafo se da como parte de la entrada, su separador puede encontrarse en tiempo lineal . Los grafos de género también tienen separadores de aristas de tamaño . ^[23] ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {gn}})}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {g\Delta n}})}$

Los grafos de género acotado forman un ejemplo de una familia de grafos cerrados bajo la operación de tomar menores , y los teoremas de separadores también se aplican a familias de grafos menores-cerrados arbitrarios. En particular, si una familia de grafos tiene un menor prohibido con vértices, entonces tiene un separador con vértices, y dicho separador se puede encontrar a tiempo para cualquier . ^[24] ${\displaystyle h}$ ${\displaystyle O(h{\sqrt {n}})}$ ${\displaystyle O(n^{1+\varepsilon })}$ ${\displaystyle \varepsilon >0}$

Un gráfico de intersección de discos, con la mayoría de los discos cubriendo cualquier punto del plano. ${\displaystyle k=5}$

El método de separador circular de Miller et al. (1997) se generaliza a los grafos de intersección de cualquier sistema de bolas de dimensión - con la propiedad de que cualquier punto en el espacio está cubierto por, como máximo, un número constante de bolas, a los grafos de vecino más cercano en dimensiones - , ^[10] y a los grafos que surgen de mallas de elementos finitos . ^[25] Los separadores de esferas construidos de esta manera dividen el grafo de entrada en subgrafos de, como máximo, vértices. El tamaño de los separadores para los grafos de intersección de bolas de - capas y para los grafos de vecino más cercano es . ^[10] ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle n(d+1)/(d+2)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle O(k^{1/d}n^{1-1/d})}$

Si una familia hereditaria de grafos tiene un teorema separador con separadores de tamaño , para algunos , entonces necesariamente tiene expansión polinómica , un límite polinómico en la densidad de sus menores superficiales . Por el contrario, los grafos con expansión polinómica tienen teoremas separadores sublineales. ^[26] ${\displaystyle n^{c}}$ ${\displaystyle c<1}$

Aplicaciones

Algoritmos de dividir y vencer

Las descomposiciones con separadores pueden ser útiles para diseñar algoritmos eficientes de división y conquista 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 dígrafo planar ponderado. Esto se puede resolver siguiendo los pasos siguientes:

• Particionar el gráfico dado en tres subconjuntos , , de acuerdo con el teorema del separador planar ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle B}$
• Busque recursivamente los ciclos más cortos en y ${\displaystyle A}$ ${\displaystyle B}$
• Utilice el algoritmo de Dijkstra para encontrar, para cada vértice en , el ciclo más corto que pasa por en . ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle G}$
• Devuelve el ciclo más corto encontrado mediante los pasos anteriores.

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

Un algoritmo más rápido para el mismo problema de ciclo más corto, que se ejecuta en tiempo , fue proporcionado 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 pertenecen a una sola cara de los grafos dentro y fuera del separador de ciclo. Luego reemplaza las 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 plano y para combinar las distancias desde los dos subgrafos. Para grafos planos ponderados pero no dirigidos, el ciclo más corto es equivalente al corte mínimo en el grafo dual y se puede encontrar en tiempo, ^[27] y el ciclo más corto en un grafo plano no dirigido no ponderado (su circunferencia ) se puede encontrar en tiempo . ^[28] (Sin embargo, el algoritmo más rápido para grafos no ponderados no se basa en el teorema del separador). ${\displaystyle O(n\log ^{3}n)}$ ${\displaystyle S}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n\log \log n)}$ ${\displaystyle O(n)}$

Frederickson propuso otro algoritmo más rápido para las rutas más cortas de una sola fuente al implementar el 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 lleva tiempo en un 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 límite de las regiones que lo contienen. El método utiliza la noción de una -división de un grafo de -nodos que es una división del grafo en regiones, cada una de las cuales contiene nodos que incluyen nodos límite. Frederickson demostró que una -división se puede encontrar en el tiempo mediante la aplicación recursiva del teorema del separador. ${\displaystyle O(n{\sqrt {\log n}})}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle O(n/r)}$ ${\displaystyle O(r)}$ ${\displaystyle O({\sqrt {r}})}$ ${\displaystyle r}$ ${\displaystyle O(n\log n)}$

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

1. Fase de preprocesamiento: Particionar el gráfico en subconjuntos cuidadosamente seleccionados de vértices 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 están en el subconjunto. Esta fase requiere que un gráfico plano se transforme en sin ningún vértice que 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 gráfico resultante será , donde es el número de vértices en . Esta fase también asegura las siguientes propiedades de una división adecuada. Una división adecuada de un gráfico plano es una división tal que, ${\displaystyle G_{0}}$ ${\displaystyle G}$ ${\displaystyle n\leq 6n_{0}-12}$ ${\displaystyle n_{0}}$ ${\displaystyle G_{0}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$
   • Cada vértice límite está contenido en tres regiones como máximo, y
   • Cualquier región que no esté conectada consta de componentes conectados, todos los cuales comparten vértices límite 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 hasta cada vértice del subconjunto. Cuando un vértice del subconjunto está cerrado, la distancia tentativa debe actualizarse para todos los vértices del subconjunto de modo que exista una ruta desde hasta . ${\displaystyle v}$ ${\displaystyle d(w)}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$
   • Limpieza: determinar las distancias más cortas a cada vértice restante.

Henzinger et al. extendieron la técnica de división de Frederickson para el algoritmo de ruta más corta de fuente única en grafos planares para longitudes de aristas no negativas y propusieron un algoritmo de tiempo lineal . ^[30] Su método generaliza la noción de divisiones de grafos de Frederickson de modo que ahora una división de un grafo de nodos es una división en regiones, cada una conteniendo nodos, cada uno teniendo como máximo nodos límite. Si una división se divide repetidamente en regiones más pequeñas, eso se llama división recursiva. Este algoritmo usa aproximadamente niveles de divisiones, donde denota la función logaritmo iterada . La división recursiva está representada por un árbol con raíz cuyas hojas están etiquetadas por una arista distinta de . La raíz del árbol representa la región que consiste en todos los , 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. ${\displaystyle r}$ ${\displaystyle (r,s)}$ ${\displaystyle n}$ ${\displaystyle O(n/r)}$ ${\displaystyle r^{O(1)}}$ ${\displaystyle s}$ ${\displaystyle (r,s)}$ ${\displaystyle \log ^{*}n}$ ${\displaystyle \log ^{*}}$ ${\displaystyle G}$ ${\displaystyle G}$

La disección anidada es una variación de la eliminación gaussiana basada en el método de dividir y vencer para resolver sistemas simétricos dispersos de ecuaciones lineales con una estructura de gráfico plana, como los que surgen del método de elementos finitos . Implica encontrar un separador para el gráfico 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 distintos de cero de la descomposición de Cholesky resultante de la matriz) es , ^[32] lo que permite que este método sea competitivo con los métodos iterativos para los mismos problemas. ^[31] ${\displaystyle O(n\log n)}$

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

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

• Llamada recursiva: la primera etapa calcula recursivamente las distancias dentro de cada gráfico . ${\displaystyle r}$ ${\displaystyle G_{i}}$
• Distancias entre los límites de las partes: para cada gráfico, calcule todas las distancias entre los nodos de los límites. Esto lleva tiempo. ${\displaystyle G_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle O(n\log n)}$
• Distancias límite entre partes de una sola fuente: una ruta más corta en pasa de ida y vuelta entre y para calcular las distancias en desde a todos los nodos límite. Las iteraciones alternas utilizan las distancias de todos los límites en y . La cantidad de iteraciones es , y el tiempo total para esta etapa es donde es la función inversa de Ackermann . ${\displaystyle G}$ ${\displaystyle G_{0}}$ ${\displaystyle G_{1}}$ ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle G_{0}}$ ${\displaystyle G_{1}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n\alpha (n))}$ ${\displaystyle \alpha (n)}$
• 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 desde hasta todos los nodos. Esta etapa lleva tiempo. ${\displaystyle G}$ ${\displaystyle r}$ ${\displaystyle O(n\log n)}$
• Reenraizamiento de distancias de una sola fuente: las distancias desde en se transforman en longitudes no negativas y, nuevamente, se utiliza el algoritmo de Dijkstra para calcular las distancias desde . Esta etapa requiere tiempo. ${\displaystyle r}$ ${\displaystyle G}$ ${\displaystyle s}$ ${\displaystyle O(n\log n)}$

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

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

Solución exacta de problemas de optimización NP-hard

Al utilizar programación dinámica en una descomposición en árbol o descomposición en rama de un grafo plano, muchos problemas de optimización NP-hard pueden resolverse en tiempo exponencial en o . Por ejemplo, los límites de esta forma son conocidos para encontrar conjuntos independientes máximos , árboles de Steiner y ciclos hamiltonianos , y para resolver el problema del viajante de comercio en grafos planos. ^[38] Se pueden utilizar métodos similares que involucran teoremas de separadores para grafos geométricos para resolver el problema del viajante de comercio euclidiano y los problemas de construcción de árboles de Steiner en límites de tiempo de la misma forma. ^[39] ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}\log n}$

Para problemas parametrizados que admiten una kernelización que preserva la planaridad y reduce el gráfico de entrada a un núcleo de tamaño lineal en el parámetro de entrada, este enfoque se puede utilizar para diseñar algoritmos manejables con parámetros fijos cuyo tiempo de ejecución depende polinomialmente del tamaño del gráfico de entrada y exponencialmente de , donde es el parámetro del algoritmo. Por ejemplo, los límites de tiempo de esta forma son conocidos por encontrar cubiertas de vértices y conjuntos dominantes de tamaño . ^[40] ${\displaystyle {\sqrt {k}}}$ ${\displaystyle k}$ ${\displaystyle k}$

Algoritmos de aproximación

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-hard en grafos planares como encontrar el conjunto independiente máximo . Específicamente, al truncar una jerarquía de separadores en un nivel apropiado, uno puede encontrar un separador de tamaño cuya eliminación divide el grafo en subgrafos de tamaño como máximo , para cualquier constante . Por el teorema de los cuatro colores , existe un conjunto independiente de tamaño al menos , 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 pueden encontrarse independientemente en el tiempo exponencial en su tamaño. Al combinar este enfoque con métodos de tiempo lineal posteriores para la construcción de la jerarquía de separadores ^[20] y con la búsqueda en tablas para compartir el cálculo de conjuntos independientes entre subgrafos isomorfos , se puede hacer que se construyan conjuntos independientes de tamaño dentro de un factor de de óptimo, en tiempo lineal. Sin embargo, para relaciones de aproximación incluso más cercanas a uno que este factor, un enfoque posterior de Baker (1994) (basado en la descomposición de árboles pero no en separadores planares) proporciona mejores compensaciones entre tiempo y calidad de aproximación. ${\displaystyle O(n/{\sqrt {\log n}})}$ ${\displaystyle c\log n}$ ${\displaystyle c}$ ${\displaystyle n/4}$ ${\displaystyle 1-1/{\sqrt {\log n}}}$

También se han utilizado esquemas de aproximación basados ​​en separadores similares 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 ruta más corta en gráficos 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 acotado 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.

Compresión de gráficos

Los separadores se han utilizado como parte de algoritmos de compresión de datos para representar grafos planares y otros grafos separables utilizando una pequeña cantidad de bits. El principio básico de estos algoritmos es elegir un número y subdividir repetidamente el grafo planar dado utilizando separadores en subgrafos de tamaño como máximo , con vértices en los separadores. Con una elección apropiada de (como máximo proporcional al logaritmo de ) el número de subgrafos planares no isomorfos con 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 subgrafos no isomorfos posibles 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. Utilizando este método, los gráficos planares y muchas familias más restringidas de gráficos pueden ser codificados utilizando un número de bits que es óptimo en teoría de la información : si hay gráficos de -vértices en la familia de gráficos a ser representados, entonces un gráfico individual en la familia puede ser representado utilizando sólo bits. ^[42] También es posible construir representaciones de este tipo en las que uno puede probar la adyacencia entre vértices, determinar el grado de un vértice y listar vecinos de vértices en tiempo constante por consulta, aumentando la tabla de subgráficos con información tabular adicional que representa las respuestas a las consultas. ^[43] ${\displaystyle k}$ ${\displaystyle O(n/k)}$ ${\displaystyle k}$ ${\displaystyle O(n/{\sqrt {k}})}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle P_{n}}$ ${\displaystyle n}$ ${\displaystyle (1+o(1))\log _{2}P_{n}}$

Grafos universales

Un gráfico universal para una familia de gráficos es un gráfico que contiene a cada miembro de la familia como subgráficos. Se pueden utilizar separadores para mostrar que los gráficos planares de -vértice tienen gráficos universales con vértices y aristas. ^[44] ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n^{3/2})}$

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 , cuya magnitud como máximo es una constante multiplicada por , de modo que los vértices de cada grafo planar de -vértice se pueden separar en subconjuntos , , y , sin aristas de hasta , con , y con . Esto se puede demostrar utilizando la forma habitual del teorema del separador repetidamente para particionar el grafo hasta que todos los componentes de la partición se puedan organizar en dos subconjuntos de menos de vértices, y luego moviendo vértices de estos subconjuntos al separador según sea necesario hasta que tenga el tamaño dado. ${\displaystyle c}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |S|=c}$ ${\displaystyle |A|=|B|=(n-c)/2}$ ${\displaystyle n/2}$

Una vez que se muestra un teorema separador de este tipo, se puede utilizar para producir una jerarquía separadora para grafos planares de -vértice que nuevamente no depende de la estructura del grafo: la descomposición en árbol formada a partir de esta jerarquía tiene ancho y se puede utilizar 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 vértices que contiene cada grafo planar de -vértice como un subgrafo. Una construcción similar muestra que los grafos planares de grado acotado tienen grafos universales con aristas, 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 ilimitado) debe tener aristas. ^[44] ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n^{3/2})}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle \Omega (n\log n)}$

Esperet, Joret y Morin (2020) anunciaron que la construcción mediante separadores se puede mejorar, para . ${\displaystyle O(n^{3/2})}$ ${\displaystyle n^{1+o(1)}}$

Véase también

• Separador de vértices
• Separador geométrico

Notas

1. Alon, Seymour y Thomas (1990).
2. Djidjev (1982).
3. George (1973). En lugar de utilizar una fila o columna de un gráfico de cuadrícula, George divide el gráfico en cuatro partes utilizando la unión de una fila y una columna como separador.
4. Lipton y Tarjan (1979).
5. Holzer y otros (2009).
6. Miller (1986).
7. Alon, Seymour y Thomas (1994).
8. Djidjev y Venkatesan (1997).
9. Gazit y Miller (1990).
10. Miller y otros (1997).
11. Miller y col. (1997); Pach y Agarwal (1995)
12. Eppstein, Miller y Teng (1995).
13. Spielman y Teng (1996).
14. Gremban, Miller y Teng (1997).
15. Har-Peled (2011).
16. Donath y Hoffman (1972); Fiedler (1973).
17. Spielman y Teng (2007).
18. Miller (1986) demostró este resultado para grafos planares 2-conexos, y Diks et al. (1993) lo extendieron a todos los grafos planares.
19. Molinero (1986); Gazit y Miller (1990).
20. Goodrich (1995).
21. Seymour y Thomas (1994).
22. Lipton y Tarjan (1979); Erdős, Graham y Szemerédi (1976).
23. Sýkora y Vrt'o (1993).
24. Kawarabayashi y Reed (2010). Para trabajos anteriores sobre separadores en familias cerradas menores, véase Alon, Seymour y Thomas (1990), Plotkin, Rao y Smith (1994) y Reed y Wood (2009).
25. Miller y otros (1998).
26. Dvořák y Norin (2016).
27. Łącki y Sankowski (2011).
28. Chang y Lu (2011).
29. Frederickson (1987).
30. Henzinger y otros (1997).
31. George (1973).
32. Lipton, Rose y Tarjan (1979); Gilbert y Tarjan (1986).
33. Klein, Moisés y Weimann (2010).
34. Eppstein y col. (1996); Eppstein et al. (1998).
35. Lipton y Tarjan (1980).
36. Klein y col. (1994); Tazari y Müller-Hannemann (2009).
37. Frieze, Miller y Teng (1992).
38. Berna (1990); Deĭneko, Klinz y Woeginger (2006); Dorn et al. (2005); Lipton y Tarjan (1980).
39. Smith y Wormald (1998).
40. Alber, Fernau y Niedermeier (2003); Fomín y Thilikos (2006b).
41. Bar-Yehuda y Even (1982); Chiba, Nishizeki y Saito (1981).
42. Él, Kao y Lu (2000).
43. Blandford, Blelloch y Kash (2003); Blelloch y Farzan (2010).
44. Babai et al. (1982); Bhat et al. (1989); Chung (1990).

Referencias

• Alber, Jochen; Fernau, Henning; Niedermeier, Rolf (2003), "Separadores de gráficos: una vista parametrizada", Journal of Computer and System Sciences , 67 (4): 808–832, doi :10.1016/S0022-0000(03)00072-2
• Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "Un teorema separador para gráficos no planos", Journal of the American Mathematical Society , 3 (4): 801–808, doi : 10.1090/S0894-0347-1990-1065053-0
• Alon, Noga ; Seymour, Paul ; Thomas, Robin (1994), "Separadores planares", SIAM Journal on Discrete Mathematics , 7 (2): 184–193, doi :10.1137/S0895480191198768
• Arora, Sanjeev ; Grigni, Michelangelo; Karger, David; Klein, Philip; Woloszyn, Andrzej (1998), "Un esquema de aproximación en tiempo polinomial para TSP de grafos planos ponderados", Proc. 9.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '98), págs. 33–41, ISBN 9780898714104
• Babai, L. ; Chung, FRK ; Erdős, P. ; Graham, RL ; Spencer, JH (1982), "Sobre grafos que contienen todos los grafos dispersos", en Rosa, Alexander; Sabidussi, Gert ; Turgeon, Jean (eds.), Teoría y práctica de la combinatoria: una colección de artículos en honor a Anton Kotzig con motivo de su sexagésimo cumpleaños (PDF) , Annals of Discrete Mathematics, vol. 12, págs. 21–26
• Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en grafos planares", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID  9706753
• Bar-Yehuda, R.; Even, S. (1982), "Sobre la aproximación de una cubierta de vértices para gráficos planares", Actas del decimocuarto simposio anual de la ACM sobre teoría de la computación - STOC '82 , págs. 303–309, doi : 10.1145/800070.802205 , ISBN 0-89791-070-2, S2CID2820550 ​{{citation}}: CS1 maint: date and year (link)
• Bern, Marshall (1990), "Algoritmos exactos más rápidos para árboles de Steiner en redes planas", Networks , 20 (1): 109–120, doi :10.1002/net.3230200110
• Bhatt, Sandeep N.; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989), "Gráficos universales para árboles de grado acotado y grafos planares" (PDF) , SIAM Journal on Discrete Mathematics , 2 (2): 145, doi :10.1137/0402014
• Blandford, Daniel K.; Blelloch, Guy E.; Kash, Ian A. (2003), "Representaciones compactas de grafos separables", Actas del 14.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '03) (PDF) , págs. 679–688
• Blelloch, Guy E.; Farzan, Arash (2010), "Representaciones sucintas de grafos separables", en Amir, Amihood; Parida, Laxmi (eds.), Proc. 21st Symposium on Combinatorial Pattern Matching , Lecture Notes in Computer Science, vol. 6129, Springer-Verlag, págs. 138–150, Bibcode :2010LNCS.6129..138B, CiteSeerX  10.1.1.307.6710 , doi :10.1007/978-3-642-13509-5_13, ISBN 978-3-642-13508-8
• Chalermsook, Parinya; Fakcharoenphol, Jittat; Nanongkai, Danupon (2004), "Un algoritmo de tiempo casi lineal determinista para encontrar cortes mínimos en gráficos planares", Proc. 15.º Simposio ACM–SIAM sobre algoritmos discretos (SODA'04), págs. 828–829
• Chang, Hsien-Chih; Lu, Hsueh-I (2011), "Cálculo de la circunferencia de un gráfico plano en tiempo lineal", SIAM Journal on Computing , 42 (3): 1077–1094, arXiv : 1104.4892 , doi :10.1137/110832033, S2CID  2493979
• Chiba, Norishige; Nishizeki, Takao ; Saito, Nobuji (1981), "Aplicaciones del teorema del separador planar de Lipton y Tarjan" (PDF) , Journal of Information Processing , 4 (4): 203–207
• Chung, Fan RK (1990), "Teoremas del separador y sus aplicaciones", en Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (eds.), Paths, Flows, and VLSI-Layout, Algorithms and Combinatorics, vol. 9, Springer-Verlag, págs. 17–34, ISBN 978-0-387-52685-0
• Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006), "Algoritmos exactos para el problema del ciclo hamiltoniano en grafos planares", Operations Research Letters , 34 (3): 269–274, doi :10.1016/j.orl.2005.04.013
• Diks, K.; Djidjev, H. N.; Sýkora, O.; Vrt'o, I. (1993), "Separadores de aristas de grafos planos y planos exteriores con aplicaciones", Journal of Algorithms , 14 (2): 258–279, doi :10.1006/jagm.1993.1013
• Djidjev, HN (1982), "Sobre el problema de la partición de grafos planares", SIAM Journal on Algebraic and Discrete Methods , 3 (2): 229–240, doi :10.1137/0603022
• Djidjev, Hristo N.; Venkatesan, Shankar M. (1997), "Constantes reducidas para la separación de gráficos de ciclos simples", Acta Informatica , 34 (3): 231–243, doi :10.1007/s002360050082, S2CID  8406777
• Donath, WE; Hoffman, AJ (1972), "Algoritmos para la partición de gráficos y lógica informática basados ​​en vectores propios de matrices de conexión", IBM Techn. Disclosure Bull. , 15 : 938–944, citado por Spielman y Teng (2007)
• Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005), "Algoritmos exactos eficientes en grafos planares: explotación de descomposiciones de ramas de corte de esfera", Proc. 13th European Symposium on Algorithms (ESA '05) , Lecture Notes in Computer Science, vol. 3669, Springer-Verlag, págs. 95–106, doi :10.1007/11561071_11, ISBN 978-3-540-29118-3
• Dvořák, Zdeněk; Norin, Sergey (2016), "Separadores fuertemente sublineales y expansión polinomial", SIAM Journal on Discrete Mathematics , 30 (2): 1095–1101, arXiv : 1504.04821 , doi :10.1137/15M1017569, MR  3504982, S2CID  27395359
• Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F. ; Spencer, Thomas H. (1996), "Esparsificación basada en separadores. I. Pruebas de planaridad y árboles de expansión mínima", Journal of Computer and System Sciences , 52 (1): 3–27, doi : 10.1006/jcss.1996.0002
• Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F.; Spencer, Thomas H. (1998), "Esparsificación basada en separadores. II. Conectividad de aristas y vértices", SIAM Journal on Computing , 28 : 341, doi :10.1137/S0097539794269072
• Eppstein, David ; Miller, Gary L. ; Teng, Shang-Hua (1995), "Un algoritmo de tiempo lineal determinista para separadores geométricos y sus aplicaciones", Fundamenta Informaticae , 22 (4): 309–331, doi :10.3233/FI-1995-2241
• Erdős, Paul ; Graham, Ronald ; Szemerédi, Endre (1976), "Sobre grafos dispersos con caminos largos y densos", Computers and Mathematics with Applications (PDF) , Oxford: Pergamon, págs. 365–369
• Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Gráficos universales dispersos para planaridad , arXiv : 2010.05779
• Fiedler, Miroslav (1973), "Conectividad algebraica de grafos", Revista matemática checoslovaca , 23 (98): 298–305, doi : 10.21136/CMJ.1973.101168 , hdl :10338.dmlcz/101168, MR  0318007
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006a), "Nuevos límites superiores en la descomponibilidad de grafos planares" (PDF) , Journal of Graph Theory , 51 (1): 53–81, doi :10.1002/jgt.20121, S2CID  260481159
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006b), "Conjuntos dominantes en grafos planares: ancho de rama y aceleración exponencial", SIAM Journal on Computing , 36 (2): 281, doi :10.1137/S0097539702419649, S2CID  5232238
• Frederickson, Greg N. (1987), "Algoritmos rápidos para caminos más cortos en grafos planos, con aplicaciones", SIAM Journal on Computing , 16 (6): 1004–1022, doi :10.1137/0216064, MR  0917037
• Frieze, Alan ; Miller, Gary L. ; Teng, Shang-Hua (1992), "Divide y vencerás en paralelo basado en separadores en geometría computacional", Proc. 4º Simposio ACM sobre algoritmos y arquitectura paralela (SPAA '92) (PDF) , págs. 420–429, doi :10.1145/140901.141934, ISBN 0-89791-483-X, Número de identificación del sujeto  10914749
• Gazit, Hillel; Miller, Gary L. (1990), "Separadores planos y la norma euclidiana", Proc. Simposio internacional sobre algoritmos (SIGAL'90) (PDF) , Lecture Notes in Computer Science, vol. 450, Springer-Verlag, págs. 338–347, doi :10.1007/3-540-52921-7_83, ISBN 978-3-540-52921-7
• George, J. Alan (1973), "Disección anidada de una malla regular de elementos finitos", SIAM Journal on Numerical Analysis , 10 (2): 345–363, Bibcode :1973SJNA...10..345G, doi :10.1137/0710032, JSTOR  2156361
• Gilbert, John R.; Hutchinson, Joan P .; Tarjan, Robert E. (1984), "Un teorema separador para gráficos de género acotado", Journal of Algorithms , 5 (3): 391–407, doi :10.1016/0196-6774(84)90019-1, hdl : 1813/6346
• Gilbert, John R.; Tarjan, Robert E. (1986), "El análisis de un algoritmo de disección anidado", Numerische Mathematik , 50 (4): 377–404, doi :10.1007/BF01396660, S2CID  122591105
• Goodrich, Michael T. (1995), "Separadores planares y triangulación de polígonos paralelos", Journal of Computer and System Sciences , 51 (3): 374–389, doi : 10.1006/jcss.1995.1076
• Gremban, Keith D.; Miller, Gary L .; Teng, Shang-Hua (1997), "Momentos de inercia y separadores de grafos" (PDF) , Journal of Combinatorial Optimization , 1 (1): 79–104, doi :10.1023/A:1009763020645, S2CID  37829
• Har-Peled, Sariel (2011), Una prueba simple de la existencia de un separador planar , arXiv : 1105.0103 , Bibcode :2011arXiv1105.0103H
• He, Xin; Kao, Ming-Yang; Lu, Hsueh-I (2000), "Una metodología general rápida para codificaciones de grafos óptimas desde el punto de vista de la información", SIAM Journal on Computing , 30 (3): 838–846, arXiv : cs/0101021 , doi :10.1137/S0097539799359117
• Henzinger, Monika R .; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997), "Algoritmos de ruta más corta más rápidos para gráficos planares", Journal of Computer and System Sciences , 55 (1, parte 1): 3–23, doi : 10.1006/jcss.1997.1493 , MR  1473046
• Holzer, Martin; Schulz, Frank; Wagner, Dorothea ; Prasinos, Grigorios; Zaroliagis, Christos (2009), "Ingeniería de algoritmos separadores planares", Journal of Experimental Algorithmics , 14 : 1.5–1.31, doi :10.1145/1498698.1571635, S2CID  6782855
• Jordan, Camille (1869), "Sur les assemblages des lignes", Journal für die reine und angewandte Mathematik , 70 : 185-190, citado por Miller et al. (1997)
• Kawarabayashi, Ken-Ichi ; Reed, Bruce (2010), "Un teorema separador en clases menores cerradas", Proc. 51.° Simposio anual IEEE sobre fundamentos de la informática , doi :10.1109/FOCS.2010.22, S2CID  15860361
• Klein, Philip N.; Mozes, Shay; Weimann, Oren (2010), "Caminos más cortos en grafos planos dirigidos con longitudes negativas: un algoritmo lineal-espacio-temporal", ACM Transactions on Algorithms , 6 (2): Art. 30, 18, doi :10.1145/1721837.1721846, MR  2675697, S2CID  3095131 ${\displaystyle O(n\log ^{2}n)}$
• Klein, Philip; Rao, Satish; Rauch, Monika; Subramanian, Sairam (1994), "Algoritmos de ruta más corta más rápidos para gráficos planares", Proc. 26.º Simposio ACM sobre teoría de la computación (STOC '94) , págs. 27-37, doi : 10.1145/195058.195092, ISBN 0-89791-663-8, S2CID185739 ​
• Łącki, Jakub; Sankowski, Piotr (2011), "Min-cuts and shortest cycles in planar graphs in time", Proc. 19th Annual European Symposium on Algorithms , Notas de clase en informática, vol. 6942, Springer-Verlag, págs. 155-166, arXiv : 1104.4890 , doi :10.1007/978-3-642-23719-5_14, ISBN ${\displaystyle O(n\log \log n)}$ 978-3-642-23718-8, S2CID15152406 ​
• Lipton, Richard J. ; Rose, Donald J. ; Tarjan, Robert E. (1979), "Disección anidada generalizada", SIAM Journal on Numerical Analysis , 16 (2): 346–358, Bibcode :1979SJNA...16..346L, doi :10.1137/0716027, JSTOR  2156840
• Lipton, Richard J. ; Tarjan, Robert E. (1979), "Un teorema separador para grafos planares", SIAM Journal on Applied Mathematics , 36 (2): 177–189, doi :10.1137/0136016
• Lipton, Richard J. ; Tarjan, Robert E. (1980), "Aplicaciones de un teorema de separador planar", SIAM Journal on Computing , 9 (3): 615–627, doi :10.1137/0209046, S2CID  12961628
• Miller, Gary L. (1986), "Encontrar pequeños separadores de ciclos simples para gráficos planares 2-conectados" (PDF) , Journal of Computer and System Sciences , 32 (3): 265–279, doi : 10.1016/0022-0000(86)90030-9
• Miller, Gary L. ; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separadores para empaquetamientos de esferas y gráficos de vecinos más cercanos", Journal of the ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , S2CID  17331739
• Miller, Gary L. ; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1998), "Separadores geométricos para mallas de elementos finitos", SIAM Journal on Scientific Computing , 19 (2): 364–386, Bibcode :1998SJSC...19..364M, CiteSeerX  10.1.1.307.2357 , doi :10.1137/S1064827594262613
• Pach, János ; Agarwal, Pankaj K. (1995), "Teorema del separador de Lipton-Tarjan", Combinatorial Geometry , John Wiley & Sons, págs. 99-102
• Papadimitriou, CH ; Sideri, M. (1996), "El ancho de bisección de los gráficos de cuadrícula", Theory of Computing Systems , 29 (2): 97–110, doi :10.1007/BF01305310, S2CID  15617963
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Menores excluidos superficiales y descomposiciones de grafos mejoradas", Proc. 5.º Simposio ACM-SIAM sobre algoritmos discretos (SODA '94), págs. 462–470, ISBN 9780898713299
• Reed, Bruce ; Wood, David R. (2009), "Un algoritmo de tiempo lineal para encontrar un separador en un gráfico excluyendo un menor", ACM Transactions on Algorithms , 5 (4): 1–16, doi :10.1145/1597036.1597043, S2CID  760001
• Seymour, Paul D. ; Thomas, Robin (1994), "Enrutamiento de llamadas y el cazador de ratas", Combinatorica , 14 (2): 217–241, doi :10.1007/BF01215352, S2CID  7508434
• Smith, Warren D.; Wormald, Nicholas C. (1998), "Teoremas y aplicaciones de los separadores geométricos", 39.° Simposio anual sobre fundamentos de la informática (FOCS '98), 8-11 de noviembre de 1998, Palo Alto, California, EE. UU. , IEEE Computer Society, págs. 232-243, doi :10.1109/SFCS.1998.743449, S2CID  17962961
• Spielman, Daniel A. ; Teng, Shang-Hua (1996), "Empaquetaduras de discos y separadores planos", Proc. 12.º Simposio ACM sobre geometría computacional (SCG '96) (PDF) , págs. 349–358, doi :10.1145/237218.237404, ISBN 0-89791-804-5, Número de identificación del sujeto  15937001
• Spielman, Daniel A. ; Teng, Shang-Hua (2007), "Funciona la partición espectral: gráficos planares y mallas de elementos finitos", Álgebra lineal y sus aplicaciones , 421 (2–3): 284–305, doi : 10.1016/j.laa.2006.07.020
• Sýkora, Ondrej; Vrt'o, Imrich (1993), "Separadores de aristas para gráficos de género acotado con aplicaciones", Theoretical Computer Science , 112 (2): 419–429, doi : 10.1016/0304-3975(93)90031-N , hdl : 11858/00-001M-0000-0014-B6DC-6
• Tazari, Siamak; Müller-Hannemann, Matthias (2009), "Caminos más cortos en tiempo lineal en clases de grafos menores cerrados, con una aplicación a la aproximación de árboles de Steiner", Discrete Applied Mathematics , 157 (4): 673–684, doi : 10.1016/j.dam.2008.08.002
• Ungar, Peter (1951), "Un teorema sobre grafos planares", Journal of the London Mathematical Society , 1 (4): 256, doi :10.1112/jlms/s1-26.4.256
• Weimann, Oren; Yuster, Raphael (2010), "Cálculo de la circunferencia de un grafo plano en el tiempo", SIAM Journal on Discrete Mathematics , 24 (2): 609, CiteSeerX 10.1.1.156.5730 , doi :10.1137/090767868 ${\displaystyle O(n\log n)}$ 
• Wulff-Nilsen, Christian (2009), Circunferencia de un dígrafo planar con pesos de arista reales en el tiempo ${\displaystyle O(n\log ^{3}n)}$ , arXiv : 0908.0697 , Bibcode :2009arXiv0908.0697W