Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.