# Separator of a Planar Graph

There is a planar graph $G(V,E)$, for every $m$ the vertex set of the graph can be partitioned into $m$ sets $V_{1}$ .. $V_{m}$, such that for every $1 \leq i \leq m$, the graph formed on $V\setminus V_{i}$ has treewidth at most $3(m-1)$. Using the above Lemma how to show that every planar graph has a separator of size $2\sqrt{3n}+1$.

Ideas: as the partitions we can take the set of vertexes so the treewidth became $3(n-1)$ looks like it gives me nothing. The second approach we can orient the tree decomposition in a such way that the root of the the tree will be a separator for two subtree each one of them $\leq 2n/3$, this approach also goes nowhere. How to reach the result of separator of size $2\sqrt{3n}+1$

Let's develop the second idea using the assumption that $m=\sqrt{n}$. For a subtree of tree decomposition $T$, let $N(v)$ be the number of distinct vertexes in the labels of the subtree rooted at $v$. If $r$ is a root of initial tree decomposition $T$, then $N(r)=|V|$, where $V$ - vertexes of the graph $G$. Let $j$ be a tree node with $N(j) \geq 1/2$ and $N(u) \leq 1/2$ for all children $u$ of $j$. Let S, a separator be $X_{j}$, $|X_{j}| \leq 3(\sqrt{n}-1)$. Now let's make $j$ the root of $T$. So far so good, but what do you mean by $V_{i}$ is at most the average? Do separator $S$ and $V_{i}$ should be connected?

-
The quantifiers in your lemma are a bit confusing. Do you mean: For any planar graph and any $m$, there are sets $V_i$ such that, ...? – Louis Jan 30 '12 at 10:01
@Louis: Thanks for the comment, of course I should be more specific, I've changed the question. – fog Jan 30 '12 at 19:13
I think you mean $V\V_i$ as well (deleting vertices, not contracting). Is that right? – Louis Jan 30 '12 at 20:51
@Louis: of course, thanks, I've changed the post – fog Jan 31 '12 at 4:43
You 2nd idea seems fine. Just set $m=\sqrt{n}$ and then argue that an $X_i$ that is a $2/3$ separator in the tree gives a $2/3$ separator in $G[V\setminus V_i]$, so that $X_i\cup V_i$ separates $G$. Since some $V_i$ is at most the average, this gives you the bound. – Louis Jan 31 '12 at 14:55

I guess I should turn my comments into an answer. We need the following fact about tree decompositions $(X,T)$ of $G$.
Fact: Assume that $T$ has degree at most $3$, and that $X_i$ is a $2/3$ separator in $T$. Then $X_i$, taken as a vertex set is a $2/3$ separator in $G$.
Assuming the fact, we use the Lemma with $m=\sqrt{n}$, which provides us with a partition of $V$ into $\sqrt{n}$ parts $V_i$ such that $G[V\setminus V_i]$ has treewidth $3(\sqrt{n}-1)$ for all $i\in [\sqrt{n}]$. In particular, one of the $V_i$, say $V_j$ has size at most $n/\sqrt{n} = \sqrt{n}$.
According to the Fact, $G[V\setminus V_j]$ has a separator $X_k$ of size at most $3\sqrt{n}-2$. It then follows that $V_j\cup X_k$ is a separator of $G$, and this has size at most $3\sqrt{n} - 2 + \sqrt{n}$ which is good enough for the bound you want.
Thanks for the answer, I am still have a problem with average size $\sqrt{n}$, this assumption is not strong enough. – fog Feb 1 '12 at 5:15
Yes it is. Not all the $V_i$ can be bigger than the average, and we only need to use one. – Louis Feb 1 '12 at 7:53