<p>Here is a proof using a well-known hammer. </p>

<p>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.</p>

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

CC BY-SA 4.0
2018-07-14T01:45:18.483Z
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.
Chandra Chekuri
CC BY-SA 4.0
2018-07-14T09:35:30.527Z
The quoted theorem of Robertson Seymour Thomas has a relatively short self contained proof, so it is not *such* a big hammer.
daniello
CC BY-SA 4.0
2018-07-14T11:47:16.493Z
Edited to remove "big" but retained "hammer".
Chandra Chekuri
CC BY-SA 4.0
2018-07-14T13:07:04.763Z
@daniello isn't that graph minor V?
Saeed
CC BY-SA 4.0
2018-07-14T01:31:59.837Z
2018-07-14T11:46:42.850Z
2018-07-14T11:46:42.850Z
Chandra Chekuri
<p>Do any of you know a reference for the following (surprisingly tedious to prove) result? </p>

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

CC BY-SA 4.0
2018-07-12T20:21:39.587Z
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.
domotorp
CC BY-SA 4.0
2018-07-12T20:29:04.473Z
What is the exact definition of the blocks?
Sariel Har-Peled
CC BY-SA 4.0
2018-07-13T02:37:46.080Z
I think you mean a balanced vertex separator as otherwise a planar graph has a bounded degeneracy.
Saeed
CC BY-SA 4.0
2018-07-13T13:55:45.093Z
Do you really need the $+1$ inside the $O(\cdot)$?
Aryeh
CC BY-SA 4.0
2018-07-13T19:00:03.820Z
Yes. If t is zero....
Sariel Har-Peled
CC BY-SA 4.0
2018-07-13T19:02:06.027Z
@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...
Sariel Har-Peled
CC BY-SA 4.0
2018-07-13T19:10:02.503Z
Yeah, that is quite convincing.
domotorp
CC BY-SA 4.0
2018-07-13T19:50:08.900Z
Okay, I've managed to recall what I had in mind. I didn't mean blocks, but faces. The number of faces is exactly $t+1$, so you can use the separator theorem for the dual graph. And then I agree that there are some tedious details, but probably not that bad.
domotorp
CC BY-SA 4.0
2018-07-13T21:08:31.967Z
Yeh. I dont think this works either - although that is *definitely* the first thing to try. The problem is that your separator might include a face that is adjacent to many faces. Implementing its separation in the primal is going to be expensive. Also, it is not clear how to maintain the prices/number of the vertices in the primal in this process (but this is probably doable).
Sariel Har-Peled
CC BY-SA 4.0
2018-07-14T09:40:23.167Z
You may assume wlog that the graph is vertex $3$-connected (no separation of order $\leq 2$). In such graphs the minimum degree is $3$, and so the number of vertices is $O(t)$. Lipton-Tarjan then gives the bound.
daniello
<reference-request><planar-graphs><separation>
Another planar separator ref question
Sariel Har-Peled
# Another planar separator ref question

(Asked by: username_0 on 2018-07-12)

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

**Tags:** reference-request, planar-graphs, separation
> **Comments:**
> **username_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.  
> **username_0**: What is the exact definition of the blocks?  
> **username_2**: I think you mean a balanced vertex separator as otherwise a planar graph has a bounded degeneracy.  
> **username_3**: Do you really need the $+1$ inside the $O(\cdot)$?  
> **username_0**: Yes. If t is zero....  
> **username_0**: @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...  
> **username_1**: Yeah, that is quite convincing.  
> **username_1**: Okay, I've managed to recall what I had in mind. I didn't mean blocks, but faces. The number of faces is exactly $t+1$, so you can use the separator theorem for the dual graph. And then I agree that there are some tedious details, but probably not that bad.  
> **username_0**: Yeh. I dont think this works either - although that is *definitely* the first thing to try. The problem is that your separator might include a face that is adjacent to many faces. Implementing its separation in the primal is going to be expensive. Also, it is not clear how to maintain the prices/number of the vertices in the primal in this process (but this is probably doable).  
> **username_4**: You may assume wlog that the graph is vertex $3$-connected (no separation of order $\leq 2$). In such graphs the minimum degree is $3$, and so the number of vertices is $O(t)$. Lipton-Tarjan then gives the bound.  

---

## 1 answers

### Answer by username_5 on 2018-07-14. Score: 7

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

> **Comments:**
> **username_5**: 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.  
> **username_4**: The quoted theorem of Robertson Seymour Thomas has a relatively short self contained proof, so it is not *such* a big hammer.  
> **username_5**: Edited to remove "big" but retained "hammer".  
> **username_2**: @daniello isn't that graph minor V?  

---

