# Another planar separator ref question

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

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

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})$.
• 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. Commented Jul 14, 2018 at 1:45