Otra pregunta de referencia del separador plano

¿Alguno de ustedes conoce una referencia para el siguiente resultado (sorprendentemente tedioso de probar)?

Dado un gráfico plano conectado con vértices y aristas, tiene un separador de vértices de tamaño . $G$ $n$ $n+t$ $O( \sqrt{t}+1)$

reference-request planar-graphs separation Sariel Har-Peled
fuente

¿Es realmente tan tedioso? Tienes como máximo bloques

, contraelos en vértices y usa el teorema del separador ponderado para ellos. En caso de que los bloques de separación sean grandes, puede seguir destruyendo todo

t

$t$

bordes entre ellos y luego se separan arbitrariamente con dos vértices cada uno.

O (\sqrt{t})

$O(\sqrt t)$

domotorp

¿Cuál es la definición exacta de los bloques?

Sariel Har-Peled

¿Realmente necesitas el

dentro de la

+ 1

$+1$

O (\cdot)

$O(\cdot)$

Aryeh

Si. Si t es cero ...

Sariel Har-Peled

@domotorp Por cierto, no creo que su idea funcione, todo el gráfico podría ser un solo bloque, solo piense en una ruta y un borde adicional que conecte los dos puntos finales, y ellos algunos otros bordes t ...

Sariel Har-Peled

Respuestas:

Aquí hay una prueba con un conocido martillo.

Supongamos wlog que está conectado, por lo tanto, es un árbol de expansión más bordes. Claramente, cualquier ciclo en debe contener uno de estos bordes que son parte del árbol de expansión. $G$ $t+1$ $G$ $t+1$

Afirmo que el ancho de árbol de es $G$ que implicaría el separador deseado (y algo más). Para probar la afirmación Letsea el treewidth de. Luego, según un teorema de Robertson-Seymour-Thomas, dado quees plano, hay una cuadrícula menor de tamaño. Sin embargo, una cuadrícula menor de tamañotieneciclos disjuntos dey cada uno de ellos requiere uno de losbordes. Por lo tanto $O(\sqrt{t})$ $k$ $G$ $G$ $\Omega(k)$ $\Omega(k)$ $\Omega(k^2)$ $t+1$ . $k = O(\sqrt{t})$

Chandra Chekuri
fuente

El argumento anterior es un caso especial del hecho de que si el tamaño del conjunto de vértices de retroalimentación de un gráfico plano

entonces el ancho de árbol de

G

$G$

t

$t$

G

$G$

. Esto es bien conocido en la literatura del FPT, por lo que, en general, el argumento es estándar.

O (\sqrt{t})

$O(\sqrt{t})$

Chandra Chekuri

El teorema citado de Robertson Seymour Thomas tiene una prueba relativamente corta, por lo que no es un martillo tan grande.

daniello

Editado para eliminar "grande" pero retenido "martillo".

Chandra Chekuri

@daniello no es ese gráfico menor V?

Saeed