3
$\begingroup$

I can't understand the proof of The Planar Separator Theorem

Any n-vertex planar graph has a 2/3-separator containing at most $\sqrt{8n}$ vertices.

Proof of the theorem 10 Graph Separators

Let's go through the proof.

Let $G$ be an embedded planar graph with $n \geq 3$ vertices, and let $k = \sqrt{2n}$ Without loss of generality, we can assume that $G$ has no loops or parallel edges, and that every face is a triangle bounded by three distinct edges. For any simple cycle $C$ in G, let $In(C)$ and $Out(C)$ denote the vertices inside and outside $C$,r respectively. No vertex of $In(C)$ is adjacent to any vertex of $Out(C)$. Let $C$ be a simple cycle satisfying three conditions:

  1. $C$ has at most $2k$ vertices.

  2. $|Out(C)| < 2n/3$.

  3. Subject to conditions 1 and 2, the difference |In(C)| and |Out(C)| is as small as possible.

Let D be the subgraph of G in the closed interior of C. For any two vertices $u$ and $v$ in $C$, let $c(u, v)$ denote their distance in $C$, and let $d(u, v)$ denote their distance in $d$.

Claim 1. $d(u, v) = c(u, v)$ for all vertices $u$ and $v$ in $C$.

We clearly have $d(u, v) \leq c(u, v)$ for all $u$ and $v$, because $C$ is a subgraph of $D$. Suppose there are distinct vertices $u$ and $v$ such that $d(u, v) < c(u, v)$ choose such a pair so that $d(u, v)$ is minimized. Let be a shortest path from $u$ to $v$ in D. If contained any other vertex $w$ in C, then $d(u, w) + d(w, v) = d(u, v) < c(u, v) \leq c(u, w) + c(w, v)$, so either $d(u, w) < c(u, w)$ or $d(w, v) < c(w, v)$ either possibility contradicts our choice of $u$ and $v$.

enter image description here

How this is possible, take a look a at the picture. It's obviously that path in $D$ is shorter than path in $C$. The part with additional vertex $w$ wasn't understood at all, at the end we get contradiction of choice of $u$ and $v$.

Claim 2. $C$ has exactly $2k$ vertices.

I can't get it too, because the proof is based on Claim 1.

Please, can you shed light on the proof.

Thanks!

Addendum:

  1. We have 3 conditions that $C$ should satisfy
  2. For purposes of deriving a contradiction, we have assumption $|In(C)| \geq 2n/3$
  3. We choice $w$ and $v$ such that $d(u,v)$ is minimized and show that either $d(u, w) < c(u, w)$ or $d(w, v) < c(w, v)$; either possibility contradicts our choice of $u$ and $v$. But this is completely fine with minimized $d(u,w)$, what is the contradiction?
  4. It turns out that we can find a better separation $C^{+}$, which is satisfies (1.1) and (1.2)(with assumption that 2 is true, which is already mistaken), but don't satisfy (1.3), and conclusion that claim is true. But how come, what about the contradiction of our choice of $u$ and $v$?

Sorry, it's not complication in terms of mathematics, but it's really mixed up in terms of logic.

  • 0
    @WillieWong: Thank you for the comment, now I understand everything mathematically, but I still have a problem with logic. Please take a look at addendum2012-01-20

1 Answers 1

1

It doesn't contradict your choice of $u,v$. The choice of $u,v$ is to make sure that the minimum path connecting $u,v$ does not intersect $C$, so that the path connected $u,v$ divides $D$ into two (and not more) regions.

The contradiction is derived from making the difference between the number of points in In(C) and Out(C) as small as possible in the initial description of the curve $C$.

Edit: Ah, you are worried about the bit where the author assumes for contradiction...

The point is this. You have conditions

  1. $C$ has at most $2k$ vertices
  2. $Out(C)$ has at most $2n/3 - 1$ vertices
  3. Optimisation condition.

Once you've chosen such a $C$, if $In(C)$ also has at most $2n/3 -1$ vertices, then $C$ is a 2/3 planar separator with at most 2k vertices, as demanded by the theorem. So it suffices to show that it is impossible for $In(C)$ to have more than $2n/3$ vertices. To do so, the authors show that if $|In(C)| \geq 2n/3$ you will get a contradiction.

To build up the contradiction, the author shows that if $|In(C)| \geq 2n/3$ he can construct a C' such that it satisfies 1 and 2, but better optimises 3 (which would contradict our original choice of $C$ being the optimiser). The construction of C' goes basically by cutting $In(C)$ in half using a length minimizer between two points on $C$. (This is to use the fact that one of the two halves will have Interior at least $n/3$.) If the path minimizer cuts $C$ in more than two pieces, you cannot guarantee that any piece will have interior more than $2n/9$. So you need to make sure that the path minimizer only cuts $C$ in half. And so the path minimizer is required to not intersect $C$. The choice of $u,v$ and the subsequence mini proof by contradiction guarantees that.

  • 0
    that phrase refers to the two alternatives immediately prior to that phrase. Read the paper again. That entire sentence from which "either possibility... choice of u and v" is taken is a _proof by contradiction_ of the fact that **no other point on the path between u and v can lie on C**.2012-01-24