5
$\begingroup$

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?

  • 0
    @Louis, thanks you very much, I've updated the post, please take a look, there are few question2012-01-31

1 Answers 1

1

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.

  • 0
    Yes it is. Not all the $V_i$ can be bigger than the average, and we only need to use one.2012-02-01