Teorema del separador plano

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

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

Ungar (1951) demostró originalmente una forma más débil del teorema del separador con ⁠ ⁠ ${\displaystyle O({\sqrt {n}}\log ^{3/2}n)}$ vértices en el separador en lugar de ⁠ ⁠ ${\displaystyle O({\sqrt {n}})}$ , y Lipton y Tarjan (1979) demostraron por primera vez la forma con el límite asintótico estrecho en el tamaño del separador. 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 se ha mejorado y se ha extendido a ciertas clases de gráficas no planas.

La aplicación repetida del teorema del separador produce una jerarquía de separadores que puede tomar la forma de una descomposición en árbol o una descomposición en ramas del gráfico. Las jerarquías de separadores se pueden usar para diseñar algoritmos eficientes de dividir y conquistar para gráficos planos, y la programación dinámica en estas jerarquías se puede usar para diseñar tiempo exponencial y algoritmos manejables de parámetros fijos 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 .

Más allá de los gráficos planos, los teoremas del separador se han aplicado a otras clases de gráficos, incluidos los gráficos que excluyen un menor fijo , los gráficos vecinos más cercanos y las mallas de elementos finitos . La existencia de un teorema del separador para una clase de gráficos puede formalizarse y cuantificarse mediante los conceptos de ancho de árbol y expansión polinomial .

Declaración del teorema

Como se suele afirmar, el teorema del separador establece que, en cualquier grafo plano de vértices , existe una partición de los vértices de en tres conjuntos , y , de modo que cada uno de y tiene como máximo vértices, tiene vértices y hay sin bordes con un punto final adentro y un punto final adentro . No se requiere que o forme subgrafos conectados de . se llama 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 gráfico plano de vértice se pueden subdividir en dos subgrafos con aristas disjuntas y de tal manera que ambos subgrafos tengan al menos vértices y que la intersección de los conjuntos de vértices de los dos subgrafos tenga vértices en él. 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 de los cuales tiene como máximo vértices. En la otra dirección, si se le da una partición en tres conjuntos , y que cumplen las condiciones del teorema del separador plano, 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 los bordes restantes (con ambos puntos finales en ) se dividen 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: se puede obtener una partición en subconjuntos más iguales a partir de una partición menos par dividiendo repetidamente el conjuntos más grandes en la partición desigual y reagrupar los componentes conectados resultantes. ^[2] ${\displaystyle 2/3}$ ${\displaystyle (1/2,1)}$

Ejemplo

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

Considere un gráfico de cuadrícula con filas y columnas; el número de vértices es igual . Por ejemplo, en la ilustración, , y . Si es impar, hay una sola fila central, y en caso contrario hay dos filas igualmente cercanas al centro; de manera similar, si es impar, hay una sola columna central, y en caso contrario hay dos columnas igualmente cercanas al centro. Al elegir cualquiera de estas filas o columnas centrales y eliminarlas del gráfico, se 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), elegir una columna central dará un separador con vértices, y de manera similar, si elige 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 plano establece que se puede construir una partición similar en cualquier gráfico plano. El caso de los gráficos planos arbitrarios difiere del caso de los gráficos 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 conectados. ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle 2n/3}$ ${\displaystyle n/2}$ ${\displaystyle A}$ ${\displaystyle B}$

Construcciones

Capas en anchura

Lipton y Tarjan (1979) aumentan el gráfico plano dado con aristas adicionales, si es necesario, de modo que se vuelva plano máximo (cada cara en una incrustación plana es un triángulo). Luego realizan una búsqueda en amplitud , basada en un vértice arbitrario , y dividen los vértices en niveles según su distancia a . Si es el nivel medio (el nivel tal que el número de vértices en los niveles superior e inferior son como máximo ), entonces debe haber niveles y que sean pasos arriba y abajo respectivamente y que contengan vértices, respectivamente, de lo contrario habría más que los vértices en los niveles cercanos . 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 de los dos de búsqueda en amplitud. Rutas de árbol desde los puntos finales de respaldo hasta el nivel . El tamaño del separador así construido es como máximo de . 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 gráficos planos ponderados, en los que cada vértice tiene un coste no negativo. El gráfico se puede dividir en tres conjuntos , y de modo que cada uno tenga como máximo el costo total y tenga vértices, sin aristas desde y . ^[4] Al analizar más cuidadosamente una construcción de separador similar, 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: aumentan el gráfico para que sea plano máximo y construyen un árbol de búsqueda en amplitud como antes. Luego, para cada borde que no forma parte del árbol, forman un ciclo combinándose 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 planos de gran diámetro, sus experimentos indican que supera a los métodos de capas de amplitud primero de Lipton-Tarjan y Djidjev en muchos tipos de gráficos planos. ^[5] ${\displaystyle e}$ ${\displaystyle e}$

Separadores de ciclo simple

Para un gráfico que ya es plano máximo, es posible mostrar una construcción más sólida de un separador de ciclo simple , un ciclo de pequeña longitud tal que el interior y el exterior del ciclo (en la incrustación plana única del gráfico) tengan cada uno al menos la mayoría de los 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) demuestran 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 afuera , que forme una partición lo más uniforme posible entre el interior y el exterior. Muestran que estos supuestos 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 ciclo mejor). Además, debe tener longitud exactamente , ya que de lo contrario se podría mejorar reemplazando una de sus aristas por los otros dos lados de un triángulo. Si los vértices están numerados (en el sentido de las agujas del reloj) desde hasta y el vértice coincide con el vértice , entonces estos pares coincidentes se pueden conectar mediante caminos disjuntos de vértices dentro del disco, mediante una forma del teorema de Menger para gráficos planos. 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 simples 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 simples con 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 de círculos

Según el teorema de empaquetado circular de Koebe-Andreev-Thurston , cualquier gráfico plano puede representarse mediante un empaquetado de discos circulares en el plano con interiores disjuntos, de modo que dos vértices del gráfico sean adyacentes si y sólo si el par de discos correspondiente son mutuamente tangentes. Como Miller et al. (1997) muestran que, 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 los discos. ^[10] ${\displaystyle 3n/4}$ ${\displaystyle 3n/4}$ ${\displaystyle O({\sqrt {n}})}$

Para demostrar esto, Miller et al. Utilice proyección estereográfica para mapear el empaque en la superficie de una esfera unitaria en tres dimensiones. Al elegir la proyección con cuidado, el centro de la esfera se puede convertir en un punto central de los centros del disco 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 de los discos. . Si se elige uniformemente al azar un plano que pasa por el centro, se cruzará un disco con una probabilidad proporcional a su radio. Por 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 la 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 números reales no negativos está acotada 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 a 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 gráfico plano 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 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 a 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 los empaquetamientos circulares , se puede demostrar que se encuentran 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 de En el gráfico, Spielman y Teng (1996) sostienen 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 Miller et al. El argumento 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 mediante una constante elegida uniformemente en el rango . Como en Miller et al., los discos que cruzan el círculo expandido forman un separador válido y, como se espera, 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 gráfico se agrupan por las coordenadas de los vectores propios de matrices derivadas del gráfico, se han utilizado durante mucho tiempo como heurística para problemas de partición de gráficos para gráficos no planos. ^[16] Como muestran Spielman y Teng (2007), la agrupación espectral también se puede utilizar para derivar una prueba alternativa de una forma debilitada del teorema del separador plano que se aplica a gráficos planos con grado acotado. En su método, los vértices de un gráfico plano dado se ordenan por las segundas coordenadas de los vectores propios de la matriz laplaciana del gráfico, y este orden de clasificación se divide en el punto que minimiza la relación del número de aristas cortadas por la partición. al número de vértices en el lado más pequeño de la partición. Como muestran, todo gráfico plano 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, 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 bordes. Los puntos finales de estos bordes 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 plano implica separadores de aristas , pequeños conjuntos de aristas que forman un corte entre dos subconjuntos y de los vértices del gráfico. Cada uno de los dos conjuntos y debe tener un tamaño como máximo de una fracción constante del número de vértices del gráfico (convencionalmente, ambos conjuntos tienen un tamaño como máximo ), y cada vértice del gráfico pertenece exactamente a uno de y . El separador consta de aristas que tienen un punto final en y un punto final en . Los límites del tamaño de un separador de aristas implican el grado de los vértices, así como el número de vértices en el gráfico: los gráficos planos en los que un vértice tiene grado , incluidos los gráficos de rueda y de estrella , no tienen separador de aristas con un separador de aristas sublineal. número 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, cada gráfico plano con grado máximo tiene un separador de bordes 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 plano forma un separador de bordes 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 plano dado fortalece el límite para el tamaño de un separador de bordes al mostrar que cada gráfico plano tiene un separador de bordes 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 borde más pequeño que divide un gráfico en dos subgrafos de igual tamaño, cuando es un subgrafo inducido de un gráfico de cuadrícula sin agujeros o con un número constante de agujeros. Sin embargo, conjeturan que el problema es NP-completo para gráficos planos arbitrarios y muestran que la complejidad del problema es la misma para gráficos de cuadrícula con muchos agujeros arbitrarios que para gráficos planos arbitrarios. ${\displaystyle G}$ ${\displaystyle G}$

límites inferiores

Un poliedro formado reemplazando 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 la cuadrícula, donde el máximo se logra disponiéndolos en una línea diagonal cerca de una esquina de la cuadrícula. Por lo tanto, para formar un separador que separe al menos uno de los puntos de la cuadrícula restante, es necesario que haya 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 gráficos planos de vértices (para valores arbitrariamente grandes de ) tales que, para cada separador que divide el gráfico restante en subgrafos de como máximo vértices, tiene al menos . ^[2] La construcción implica aproximar una esfera mediante un poliedro convexo , reemplazando cada una de las caras del poliedro por una malla triangular y aplicando 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 separadoras

Los separadores se pueden combinar en una jerarquía de separadores de un gráfico plano, una descomposición recursiva en gráficos más pequeños. Una jerarquía de separadores puede representarse mediante un árbol binario en el que el nodo raíz representa el gráfico dado en sí, 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 gráfico dado, en el 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 gráficos 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 estas rutas se suman una serie geométrica a . Es decir, un separador formado de esta manera tiene ancho y puede usarse para mostrar que cada gráfico plano tiene ancho de árbol . ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Construir una jerarquía de separadores directamente, atravesando el árbol binario de arriba hacia abajo y aplicando un algoritmo de separador plano de tiempo lineal a cada uno de los subgrafos inducidos asociados con cada nodo del árbol binario, tomaría un total de tiempo. Sin embargo, es posible construir una jerarquía de separadores completa en tiempo lineal, utilizando el enfoque de capas de Lipton-Tarjan primero en amplitud 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 basada en separaciones en lugar de separadores, en la 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 rama. -descomposición en lugar de una descomposición de á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 un camino desde cualquier nodo hasta la raíz de la jerarquía, por lo que cualquier descomposición en rama formada de esta manera tiene ancho y cualquier gráfico plano. tiene ancho de rama . Aunque muchos otros problemas de partición de gráficos relacionados son NP-completos , incluso para gráficos planos, es posible encontrar una descomposición de rama de ancho mínimo de un gráfico plano en tiempo polinómico. ^[21] ${\displaystyle G_{1}}$ ${\displaystyle G_{2}}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$

Al aplicar 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 todo gráfico plano tiene un ancho de rama como máximo , con la misma constante que el del separador de ciclo simple. teorema de Alon et al. Dado que el ancho de árbol de cualquier gráfico es como máximo su ancho de rama, esto también muestra que los gráficos planos 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 sea el resultado de Jordan (1869) de que cualquier árbol puede dividirse en subárboles de como máximo vértices cada uno mediante la eliminación de un solo vértice. ^[10] En particular, el vértice que minimiza el tamaño máximo del componente tiene esta propiedad, ya que si no la tuviera, su vecino en el subárbol grande único formaría una partición aún mejor. Al aplicar la misma técnica a una descomposición en árbol de un gráfico arbitrario, es posible demostrar que cualquier gráfico tiene un separador de tamaño como máximo igual a su ancho de árbol . ${\displaystyle n/2}$

Si un gráfico no es plano, pero puede incrustarse en una superficie de género , entonces tiene un separador con vértices. Gilbert, Hutchinson y Tarjan (1984) prueban esto utilizando un enfoque similar al de Lipton y Tarjan (1979). Agrupan los vértices del gráfico en niveles de amplitud y encuentran dos niveles cuya eliminación deja como máximo un componente grande que consta de un pequeño número de niveles. Este componente restante se puede hacer plano eliminando una cantidad de caminos de amplitud proporcional al género, después de lo cual se puede aplicar el método Lipton-Tarjan al gráfico plano restante. El resultado se obtiene al equilibrar cuidadosamente el tamaño de los dos niveles eliminados con el número de niveles entre ellos. Si la incrustación del gráfico se proporciona como parte de la entrada, su separador se puede encontrar en tiempo lineal . Los gráficos de género también tienen separadores de tamaño en los bordes . ^[23] ${\displaystyle G}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {gn}})}$ ${\displaystyle g}$ ${\displaystyle O({\sqrt {g\Delta n}})}$

Los gráficos de género acotado forman un ejemplo de una familia de gráficos cerrados bajo la operación de tomar menores , y los teoremas del separador también se aplican a familias arbitrarias de gráficos cerrados menores. 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, donde como máximo los discos cubren cualquier punto del plano. ${\displaystyle k=5}$

El método del separador de círculos de Miller et al. (1997) generaliza a las gráficas de intersección de cualquier sistema de bolas -dimensionales con la propiedad de que cualquier punto en el espacio está cubierto como máximo por un número constante de bolas, a las gráficas del vecino más cercano en dimensiones, ^[10] y a las gráficas que surgen de mallas de elementos finitos . ^[25] Los separadores de esfera construidos de esta manera dividen el gráfico de entrada en subgrafos de como máximo vértices. El tamaño de los separadores para los gráficos de intersección de bolas de capas y para los gráficos del 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 gráficos tiene un teorema del separador con separadores de tamaño , para algunos , entonces necesariamente tiene expansión polinómica , un polinomio ligado a la densidad de sus menores poco profundos . Por el contrario, las gráficas con expansión polinomial tienen teoremas de separación sublineal. ^[26] ${\displaystyle n^{c}}$ ${\displaystyle c<1}$

Aplicaciones

Algoritmos de divide y vencerás

Las descomposiciones de separadores pueden ser útiles en el diseño de algoritmos eficientes de divide y vencerás para resolver problemas en gráficos planos. Por ejemplo, un problema que se puede resolver de esta manera es encontrar el ciclo más corto en un dígrafo plano ponderado. Esto se puede solucionar mediante los siguientes pasos:

• Divida el gráfico dado en tres subconjuntos , según el teorema del separador plano ${\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 a través de . ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle s}$ ${\displaystyle G}$
• Devuelve el ciclo más corto de los encontrados en 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)}$

Wulff-Nilsen (2009) propuso un algoritmo más rápido para el mismo problema de ciclo más corto, ejecutándose en el tiempo . Su algoritmo utiliza la misma estructura de dividir y conquistar 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 gráficos 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 gráfico plano y combinar las distancias desde los dos subgrafos. Para gráficos planos ponderados pero no dirigidos, el ciclo más corto es equivalente al corte mínimo en el gráfico dual y se puede encontrar en el tiempo, ^[27] y el ciclo más corto en un gráfico plano no ponderado y no dirigido (su circunferencia ) se puede encontrar en el tiempo . ^[28] (Sin embargo, el algoritmo más rápido para gráficos 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 los caminos más cortos de una sola fuente mediante la implementación del teorema del separador en gráficos planos. ^[29] Esta es una mejora del algoritmo de Dijkstra con búsqueda iterativa en un subconjunto de vértices cuidadosamente seleccionado. Esta versión lleva tiempo en un gráfico de vértices. Los separadores se utilizan para encontrar una división de un gráfico, 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 algún borde de la región incide sobre el nodo. Un nodo contenido en más de una región se denomina nodo límite de las regiones que lo contienen. El método utiliza la noción de división de un gráfico de nodos, que es una división del gráfico en regiones, cada una de las cuales contiene nodos, incluidos los nodos límite. Frederickson demostró que se puede encontrar una división 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: divida el gráfico en subconjuntos de vértices cuidadosamente seleccionados y determine 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 se transforme un gráfico plano 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 gráfico resultante será , donde es el número de vértices en . Esta fase también garantiza 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 del límite está contenido en como máximo tres regiones, 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:
   • Empuje principal: encuentre las distancias más cortas desde la fuente hasta cada vértice del subconjunto. Cuando se cierra un vértice del subconjunto, 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: determine las distancias más cortas a cada vértice restante.

Henzinger et al. amplió la técnica de división de Frederickson para el algoritmo de ruta más corta de una sola fuente en gráficos planos para longitudes de borde no negativas y propuso un algoritmo de tiempo lineal . ^[30] Su método generaliza la noción de Frederickson de divisiones de gráficos de modo que ahora una división de un gráfico de nodos es una división en regiones, cada una de las cuales contiene nodos y cada una tiene como máximo nodos límite. Si una división se divide repetidamente en regiones más pequeñas, se denomina división recursiva. Este algoritmo utiliza aproximadamente niveles de divisiones, donde denota la función logarítmica iterada . La división recursiva está representada por un árbol enraizado cuyas hojas están etiquetadas por un borde distinto . La raíz del árbol representa la región que consta de todos , 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 un borde. ${\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 división y conquista basada en separador de eliminación gaussiana para resolver sistemas simétricos dispersos de ecuaciones lineales con una estructura de gráfico plano, 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 métodos iterativos para los mismos problemas. ^[31] ${\displaystyle O(n\log n)}$

Klein, Mozes y Weimann ^[33] proporcionaron un algoritmo de espacio lineal en tiempo para encontrar las distancias de camino más cortas desde un vértice de origen a todos los demás vértices para un gráfico plano dirigido con longitudes de arco positivas y negativas que no contienen ciclos negativos. Su algoritmo utiliza separadores de gráficos planos para encontrar una curva de Jordan que pasa por nodos (y sin arcos) de modo que entre los nodos y estén encerrados por . Los nodos por los que pasa son nodos límite . El gráfico original se separa en dos subgrafos y se corta la incrustación plana y se duplican los nodos límite. Los nodos de límite en cada gráfico 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 de forma recursiva las distancias dentro de cada gráfico . ${\displaystyle r}$ ${\displaystyle G_{i}}$
• Distancias de límites dentro de la parte: para cada gráfico, calcule todas las distancias entre los nodos de límites. Esto lleva tiempo. ${\displaystyle G_{i}}$ ${\displaystyle G_{i}}$ ${\displaystyle O(n\log n)}$
• Distancias de límites entre partes de una sola fuente: una ruta más corta en pasos de ida y vuelta entre y para calcular las distancias desde a todos los nodos de límite. Las iteraciones alternas utilizan todas las distancias límite en y . El número de iteraciones es y el tiempo total para esta etapa es donde está la función de Ackermann inversa . ${\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 Gi _,  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 in se transforman en longitudes no negativas y nuevamente se utiliza el algoritmo de Dijkstra para calcular 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 gráfico dirigido con longitudes de arco , una función de precio es una función desde los nodos de hasta 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 puede resolverse usando 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 conquistar basado en separadores también se ha utilizado para diseñar estructuras de datos para algoritmos de gráficos dinámicos ^[34] y ubicación de puntos , ^[35] algoritmos para triangulación de polígonos , ^[20] caminos más cortos , ^[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 plano. ^[35]

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

Al utilizar programación dinámica en una descomposición de árbol o descomposición en rama de un gráfico plano, muchos problemas de optimización NP-hard se pueden resolver en tiempo exponencial en o . Por ejemplo, los límites de esta forma son conocidos por encontrar conjuntos independientes máximos , árboles de Steiner y ciclos hamiltonianos , y por resolver el problema del viajante en gráficos planos. ^[38] Se pueden utilizar métodos similares que involucran teoremas de separador para gráficos geométricos para resolver el problema del viajante euclidiano y los problemas de construcción del árbol 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 kernel de tamaño lineal en el parámetro de entrada, este enfoque se puede utilizar para diseñar algoritmos manejables de parámetros fijos cuyo tiempo de ejecución depende polinomialmente del tamaño del gráfico. gráfico de entrada y exponencialmente en , donde está el parámetro del algoritmo. Por ejemplo, los límites de tiempo de esta forma son conocidos por encontrar coberturas de vértices y conjuntos de tamaño dominantes . ^[40] ${\displaystyle {\sqrt {k}}}$ ${\displaystyle k}$ ${\displaystyle k}$

Algoritmos de aproximación

Lipton y Tarjan (1980) observaron que el teorema del separador se puede utilizar para obtener esquemas de aproximación de tiempo polinomial para problemas de optimización NP-duro en gráficos planos, 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 cuya eliminación divide el gráfico en subgrafos de tamaño como máximo , para cualquier constante . Según 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 se pueden encontrar de forma independiente en el 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 la búsqueda de tablas para compartir el cálculo de conjuntos independientes entre subgrafos isomórficos , se puede construir conjuntos independientes de tamaño dentro de un factor 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 planos) proporciona mejores compensaciones entre el tiempo y la calidad de la 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 similares basados ​​en separadores para aproximar otros problemas difíciles, como la cobertura de vértices . ^[41] Arora y cols. (1998) utilizan separadores de una manera diferente para aproximar el problema del viajante para la métrica del camino más corto en gráficos planos 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 a las óptimas. recorrido.

Compresión de gráficos

Los separadores se han utilizado como parte de algoritmos de compresión de datos para representar gráficos planos y otros gráficos separables utilizando una pequeña cantidad de bits. El principio básico de estos algoritmos es elegir un número y subdividir repetidamente el gráfico plano dado usando separadores en subgráficos de tamaño como máximo , con vértices en los separadores. Con una elección adecuada de (como máximo proporcional al logaritmo de ), el número de subgrafos planos de vértices no isomórficos es significativamente menor que el número de subgrafos en la descomposición, por lo que el gráfico se puede comprimir construyendo una tabla de todos los posibles. subgrafos no isomórficos y que representan cada subgrafo en la descomposición del separador por su índice en la tabla. El resto del gráfico, formado por los vértices separadores, se puede representar explícitamente o utilizando una versión recursiva de la misma estructura de datos. Usando este método, los gráficos planos y muchas más familias restringidas de gráficos se pueden codificar usando un número de bits que es óptima desde el punto de vista de la información : si hay gráficos de vértices en la familia de gráficos que se van a representar, entonces un gráfico individual en la familia se puede representar utilizando sólo 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 enumerar los vecinos de los vértices en tiempo constante por consulta, aumentando la tabla de subgrafos con información tabular adicional. representando 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 todos los miembros como subgrafos. Se pueden utilizar separadores para mostrar que los gráficos planos de vértices 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 gráfico: existe un número , cuya magnitud como máximo es constante , tal que los vértices de cada gráfico plano de vértice se puede separar en subconjuntos , y , sin aristas desde a , con y con . Esto se puede demostrar usando la forma habitual del teorema del separador repetidamente para dividir el gráfico hasta que todos los componentes de la partición puedan organizarse en dos subconjuntos de menos de vértices, y luego moviendo los vértices de estos subconjuntos al separador según sea necesario hasta que tiene el tamaño indicado. ${\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 de separación de este tipo, se puede usar para producir una jerarquía de separación para gráficos planos de vértices que nuevamente no depende de la estructura del gráfico: la descomposición en árbol formada a partir de esta jerarquía tiene ancho y se puede usar para cualquier gráfico plano. El conjunto de todos los pares de vértices en esta descomposición de árbol que pertenecen a un nodo común de la descomposición de árbol forma un gráfico trivialmente perfecto con vértices que contiene cada gráfico plano de vértice como un subgrafo. Una construcción similar muestra que los gráficos planos de grados acotados tienen gráficos universales con aristas, donde la constante oculta en la notación O depende del límite de grados. Cualquier gráfico universal para gráficos planos (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 & Morin (2020) anunciaron que se puede mejorar la construcción mediante separadores, a . ${\displaystyle O(n^{3/2})}$ ${\displaystyle n^{1+o(1)}}$

Ver también

• Separador de vértices
• Separador geométrico

Notas

1. Alon, Seymour y Thomas (1990).
2. Djijjev (1982).
3. Jorge (1973). En lugar de usar una fila o columna de un gráfico de cuadrícula, George divide el gráfico en cuatro partes usando la unión de una fila y una columna como separador.
4. Lipton y Tarjan (1979).
5. Holzer y col. (2009).
6. Molinero (1986).
7. Alon, Seymour y Thomas (1994).
8. Djijev y Venkatesan (1997).
9. Gazit y Miller (1990).
10. Miller y col. (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 gráficos planos biconexos, y Diks et al. (1993) lo ampliaron a todos los gráficos planos.
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 con menores, consulte Alon, Seymour y Thomas (1990), Plotkin, Rao y Smith (1994) y Reed y Wood (2009).
25. Miller y col. (1998).
26. Dvořák y Norin (2016).
27. Łącki y Sankowski (2011).
28. Chang y Lu (2011).
29. Federicoson (1987).
30. Henzinger y col. (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. Friso, 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 e incluso (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. (mil novecientos ochenta y dos); 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
• Alón, Noga ; Seymour, Pablo ; Thomas, Robin (1990), "Un teorema del separador para gráficos no planos", Revista de la Sociedad Matemática Estadounidense , 3 (4): 801–808, doi : 10.1090/S0894-0347-1990-1065053-0
• Alón, Noga ; Seymour, Pablo ; Thomas, Robin (1994), "Separadores planos", Revista SIAM de Matemáticas Discretas , 7 (2): 184–193, doi :10.1137/S0895480191198768
• Arora, Sanjeev ; Grigni, Miguel Ángel; Karger, David; Klein, Felipe; Woloszyn, Andrzej (1998), "Un esquema de aproximación en tiempo polinomial para el gráfico plano ponderado TSP", Proc. Noveno 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 gráficos que contienen todos los gráficos 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 gráficos planos", 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 cobertura de vértices para gráficos planos", Actas del decimocuarto simposio anual ACM sobre teoría de la computación - STOC '82 , págs. 303–309, doi : 10.1145/800070.802205 , ISBN 0-89791-070-2, S2CID  2820550{{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, pies ; Rosenberg, Arnold L. (1989), "Gráficos universales para árboles de grados acotados y gráficos planos" (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 gráficos separables", Proc. 14º Simposio ACM-SIAM sobre algoritmos discretos (SODA '03) (PDF) , págs. 679–688
• Blelloch, Guy E.; Farzan, Arash (2010), "Representaciones sucintas de gráficos separables", en Amir, Amihood; Parida, Laxmi (eds.), Proc. XXI Simposio sobre coincidencia de patrones combinatorios , Apuntes de conferencias sobre informática, 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 determinista casi lineal para encontrar cortes mínimos en gráficos planos", 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 plano 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.), Rutas, flujos y diseño VLSI, algoritmos y combinatoria, 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 gráficos planos", Operations Research Letters , 34 (3): 269–274, doi :10.1016/j.orl.2005.04.013
• Diks, K.; Djijev, HN; Sykora, O.; Vrt'o, I. (1993), "Separadores de bordes de gráficos planos y externos 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 gráficos planos", Revista SIAM sobre métodos algebraicos y discretos , 3 (2): 229–240, doi :10.1137/0603022
• Djijjev, Hristo N.; Venkatesan, Shankar M. (1997), "Constantes reducidas para la separación de gráficos de ciclo simple", Acta Informatica , 34 (3): 231–243, doi :10.1007/s002360050082, S2CID  8406777
• Donath, NOSOTROS; 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. Toro de Divulgación. , 15 : 938–944, citado por Spielman y Teng (2007)
• Dorn, Federico; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005), "Algoritmos exactos eficientes en gráficos planos: explotación de descomposiciones de ramas de corte esférico", Proc. 13º Simposio Europeo sobre Algoritmos (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 polinómica", Revista SIAM de Matemáticas Discretas , 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 bordes 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 gráficos dispersos con caminos largos y densos", Computadoras y matemáticas con aplicaciones (PDF) , Oxford: Pergamon, págs.
• Espéret, Louis; Joret, Gwenaël; Morin, Pat (2020), Gráficos universales dispersos para planaridad , arXiv : 2010.05779
• Fiedler, Miroslav (1973), "Conectividad algebraica de gráficos", Checoslovak Mathematical Journal , 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 a la descomponibilidad de gráficos planos" (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 gráficos planos: 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 gráficos planos, con aplicaciones", SIAM Journal on Computing , 16 (6): 1004–1022, doi :10.1137/0216064, MR  0917037
• Friso, Alan ; Miller, Gary L .; Teng, Shang-Hua (1992), "Divide y vencerás paralelo basado en separadores en geometría computacional", Proc. Cuarto Simposio ACM sobre arquitectura y algoritmos paralelos (SPAA '92) (PDF) , págs. 420–429, doi :10.1145/140901.141934, ISBN 0-89791-483-X, S2CID  10914749
• Gazit, Hillel; Miller, Gary L. (1990), "Separadores planos y la norma euclidiana", Proc. Simposio internacional sobre algoritmos (SIGAL'90) (PDF) , Apuntes de conferencias sobre informática, 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 de elementos finitos regular", 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 del separador para gráficas 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 planos 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 gráficos" (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 plano , arXiv : 1105.0103 , Bibcode :2011arXiv1105.0103H
• Él, Xin; Kao, Ming-Yang; Lu, Hsueh-I (2000), "Una metodología general rápida para codificaciones de gráficos teóricamente óptimas de la información", SIAM Journal on Computing , 30 (3): 838–846, arXiv : cs/0101021 , doi :10.1137/S0097539799359117
• Henzinger, Monika R .; Klein, Felipe; Rao, Satish; Subramanian, Sairam (1997), "Algoritmos más rápidos de ruta más corta para gráficos planos", Journal of Computer and System Sciences , 55 (1, parte 1): 3–23, doi : 10.1006/jcss.1997.1493 , MR  1473046
• Holzer, Martín; Schulz, Frank; Wagner, Dorotea ; Prasinos, Grigorios; Zaroliagis, Christos (2009), "Algoritmos de separación plana de ingeniería", 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 del separador en clases cerradas menores", Proc. 51.º Simposio anual del IEEE sobre fundamentos de la informática , doi :10.1109/FOCS.2010.22, S2CID  15860361
• Klein, Philip N.; Moisés, Shay; Weimann, Oren (2010), "Rutas más cortas en gráficos planos dirigidos con longitudes negativas: un algoritmo de espacio-tiempo lineal", ACM Transactions on Algorithms , 6 (2): art. 30, 18, doi :10.1145/1721837.1721846, SEÑOR  2675697, S2CID  3095131 ${\displaystyle O(n\log ^{2}n)}$
• Klein, Felipe; Rao, Satish; Rauch, Mónica; Subramanian, Sairam (1994), "Algoritmos más rápidos de camino más corto para gráficos planos", 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, S2CID  185739
• Łącki, Jakub; Sankowski, Piotr (2011), "Cortes mínimos y ciclos más cortos en gráficos planos en el tiempo", Proc. XIX Simposio europeo anual sobre algoritmos , Apuntes de conferencias sobre 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, S2CID  15152406
• Lipton, Richard J .; Rosa, Donald J.; Tarjan, Robert E. (1979), "Disección anidada generalizada", Revista SIAM de análisis numérico , 16 (2): 346–358, Bibcode :1979SJNA...16..346L, doi :10.1137/0716027, JSTOR  2156840
• Lipton, Richard J .; Tarjan, Robert E. (1979), "Un teorema del separador para gráficos planos", Revista SIAM de Matemáticas Aplicadas , 36 (2): 177–189, doi :10.1137/0136016
• Lipton, Richard J .; Tarjan, Robert E. (1980), "Aplicaciones de un teorema del separador plano", SIAM Journal on Computing , 9 (3): 615–627, doi :10.1137/0209046, S2CID  12961628
• Miller, Gary L. (1986), "Encontrar pequeños separadores de ciclo simples para gráficos planos conectados por 2" (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", Geometría combinatoria , John Wiley & Sons, págs.
• Papadimitriou, CH ; Sideri, M. (1996), "El ancho de bisección de los gráficos de cuadrícula", Teoría de los sistemas informáticos , 29 (2): 97–110, doi :10.1007/BF01305310, S2CID  15617963
• Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Menores excluidos superficiales y descomposiciones gráficas mejoradas", Proc. Quinto Simposio ACM-SIAM sobre algoritmos discretos (SODA '94), págs. 462–470, ISBN 9780898713299
• Caña, Bruce ; Wood, David R. (2009), "Un algoritmo de tiempo lineal para encontrar un separador en un gráfico que excluye un menor", ACM Transactions on Algorithms , 5 (4): 1–16, doi :10.1145/1597036.1597043, S2CID  760001
• Seymour, Paul D .; Thomas, Robin (1994), "El 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 del separador geométrico", 39º Simposio anual sobre fundamentos de la informática (FOCS '98), 8 al 11 de noviembre de 1998, Palo Alto, California, EE. UU. , IEEE Computer Society, págs. 232–243, dirección : 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, S2CID  15937001
• Spielman, Daniel A .; Teng, Shang-Hua (2007), "Trabajos de partición espectral: gráficos planos y mallas de elementos finitos", Álgebra lineal y sus aplicaciones , 421 (2–3): 284–305, doi : 10.1016/j.laa.2006.07.020
• Sykora, Ondrej; Vrt'o, Imrich (1993), "Separadores de bordes para gráficos de género acotado con aplicaciones", Informática teórica , 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), "Rutas más cortas en tiempo lineal en clases de gráficos menores cerrados, con una aplicación a la aproximación del árbol de Steiner", Matemáticas Aplicadas Discretas , 157 (4): 673–684, doi : 10.1016/j. presa.2008.08.002
• Ungar, Peter (1951), "Un teorema sobre gráficos planos", Revista de la Sociedad Matemática de Londres , 1 (4): 256, doi :10.1112/jlms/s1-26.4.256
• Weimann, Oren; Yuster, Raphael (2010), "Calcular la circunferencia de un gráfico plano en el tiempo", Revista SIAM de Matemáticas Discretas , 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 plano con pesos de borde reales en el tiempo ${\displaystyle O(n\log ^{3}n)}$ , arXiv : 0908.0697 , Bibcode : 2009arXiv0908.0697W