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)$.

  • $\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
    Commented Jul 12, 2018 at 20:21
  • $\begingroup$ What is the exact definition of the blocks? $\endgroup$ Commented Jul 12, 2018 at 20:29
  • 1
    $\begingroup$ Do you really need the $+1$ inside the $O(\cdot)$? $\endgroup$
    – Aryeh
    Commented Jul 13, 2018 at 13:55
  • 2
    $\begingroup$ Yes. If t is zero.... $\endgroup$ Commented Jul 13, 2018 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$ Commented Jul 13, 2018 at 19:02

1 Answer 1


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})$.

  • 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$ Commented Jul 14, 2018 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
    Commented Jul 14, 2018 at 9:35
  • 1
    $\begingroup$ Edited to remove "big" but retained "hammer". $\endgroup$ Commented Jul 14, 2018 at 11:47
  • $\begingroup$ @daniello isn't that graph minor V? $\endgroup$
    – Saeed
    Commented Jul 14, 2018 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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