Separador de un Plano Gráfico

Question

Hay un plano gráfico de $G(V,E)$, para cada $m$ el conjunto de vértices de la gráfica se puede dividir en $m$ define $V_{1}$ .. $V_{m}$, tal que para cada a $1 \leq i \leq m$, el gráfico formado en $V\setminus V_{i}$ ha treewidth en la mayoría de las $3(m-1)$. Usando el Lema de cómo mostrar que cada plano gráfico tiene un separador de tamaño $2\sqrt{3n}+1$.

Ideas: como las particiones que puede tomar el conjunto de vértices de modo que el treewidth se convirtió $3(n-1)$ parece que me da nada. El segundo enfoque nos puede orientar sobre el árbol de descomposición, de tal forma que la raíz del árbol será un separador para dos subárbol cada uno de ellos $\leq 2n/3$, este enfoque también se va a ninguna parte. Cómo llegar a el resultado de separador de tamaño $2\sqrt{3n}+1$

Vamos a desarrollar la segunda idea mediante la suposición de que $m=\sqrt{n}$. Para un subárbol del árbol de descomposición $T$, vamos a $N(v)$ ser el número de los distintos vértices en las etiquetas de los subárbol cuya raíz está en $v$. Si $r$ es una raíz de árbol inicial de descomposición $T$, $N(r)=|V|$ donde $V$ - vértices de la gráfica de $G$. Deje $j$ ser un nodo de árbol con $N(j) \geq 1/2$ $N(u) \leq 1/2$ para todos los niños $u$$j$. Vamos, un separador de ser $X_{j}$, $|X_{j}| \leq 3(\sqrt{n}-1)$. Ahora vamos a hacer $j$ la raíz de $T$. Hasta aquí bien, pero ¿qué quiere decir $V_{i}$ es en la mayoría de los media? Hacer separador de $S$ $V_{i}$ debe estar conectado?

Answer 1

Supongo que debería girar mis comentarios en una respuesta. Necesitamos el siguiente hecho sobre el árbol de la descomposiciones $(X,T)$$G$.

Hecho: Suponga que $T$ tiene un grado en la mayoría de las $3$, $X_i$ $2/3$ separador en $T$. A continuación,$X_i$, tomado como un conjunto de vértices es un $2/3$ separador en $G$.

Asumiendo el hecho, utilizamos el Lema con $m=\sqrt{n}$, el cual nos provee con una partición de $V$ a $\sqrt{n}$ partes $V_i$ tal que $G[V\setminus V_i]$ ha treewidth $3(\sqrt{n}-1)$ todos los $i\in [\sqrt{n}]$. En particular, uno de los $V_i$, decir $V_j$ tiene de tamaño en la mayoría de las $n/\sqrt{n} = \sqrt{n}$.

De acuerdo con el Hecho de, $G[V\setminus V_j]$ tiene un separador de $X_k$ del tamaño en la mayoría de los $3\sqrt{n}-2$. A continuación, se deduce que el $V_j\cup X_k$ es un separador de $G$, y este tiene un tamaño en la mayoría de las $3\sqrt{n} - 2 + \sqrt{n}$ que es lo suficientemente bueno para el obligado que usted desea.