8
$\begingroup$

Do any of you know a reference for the following (surprisingly tedious to prove) result?

Given a connected planar graph $G$ with $n$ vertices and $n+t$ edges, it has a vertex separator of size $O( \sqrt{t}+1)$.

$\endgroup$
  • $\begingroup$ Is it really that tedious? You have at most $t$ blocks, contract them into vertices and use the weighted separator theorem for them. In case the separating blocks are large, you can keep destroy all $O(\sqrt t)$ edges among them and then separate each arbitrarily with two vertices each. $\endgroup$ – domotorp Jul 12 '18 at 20:21
  • $\begingroup$ What is the exact definition of the blocks? $\endgroup$ – Sariel Har-Peled Jul 12 '18 at 20:29
  • 1
    $\begingroup$ Do you really need the $+1$ inside the $O(\cdot)$? $\endgroup$ – Aryeh Jul 13 '18 at 13:55
  • 2
    $\begingroup$ Yes. If t is zero.... $\endgroup$ – Sariel Har-Peled Jul 13 '18 at 19:00
  • 2
    $\begingroup$ @domotorp BTW, I dont think your idea works - the whole graph might be a single block - just think about a path, and an additional edge connecting the two endpoints, and them some other t edges... $\endgroup$ – Sariel Har-Peled Jul 13 '18 at 19:02
7
$\begingroup$

Here is a proof using a well-known hammer.

Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges which are part of the spanning tree.

I claim that the treewidth of $G$ is $O(\sqrt{t})$ which would imply the desired separator (and some more). To prove the claim let $k$ be the treewidth of $G$. Then by a theorem of Robertson-Seymour-Thomas, since $G$ is planar, there is a grid minor of size $\Omega(k)$. However a grid minor of size $\Omega(k)$ has $\Omega(k^2)$ disjoint cycles and each of them requires one of the $t+1$ edges. Hence $k = O(\sqrt{t})$.

$\endgroup$
  • 1
    $\begingroup$ The above argument is a special case of the fact that if the feedback vertex set size of a planar graph $G$ is $t$ then treewidth of $G$ is $O(\sqrt{t})$. This is well-known in FPT literature so overall the argument is standard. $\endgroup$ – Chandra Chekuri Jul 14 '18 at 1:45
  • $\begingroup$ The quoted theorem of Robertson Seymour Thomas has a relatively short self contained proof, so it is not such a big hammer. $\endgroup$ – daniello Jul 14 '18 at 9:35
  • 1
    $\begingroup$ Edited to remove "big" but retained "hammer". $\endgroup$ – Chandra Chekuri Jul 14 '18 at 11:47
  • $\begingroup$ @daniello isn't that graph minor V? $\endgroup$ – Saeed Jul 14 '18 at 13:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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