Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If $G$ has $n$ vertices, and Out(C) has $< 2n/3$, shouldn't In(C) have $\geq n/3$ vertices? (Instead of $2n/3$ as you wrote?) Also, in the first line after claim 1, you want $d \leq c$ instead of $d < c$, I expect. –  Willie Wong Jan 20 '12 at 14:42
    
You only quoted the first half of the proof for Claim 1 from the linked PDf file. Try reading on the next few sentences. The basic idea is that $C$ is assumed to satisfy three conditions (the third one, especially, is an optimisation condition). If Claim 1 were violated, then the author shows one can construct another $C^+$ that better optimises condition 3, which contradicts the assumption that $C$ is the optimiser. –  Willie Wong Jan 20 '12 at 15:02
    
@WillieWong: Thank you for the comment, now I understand everything mathematically, but I still have a problem with logic. Please take a look at addendum –  com Jan 20 '12 at 17:32

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks for the answer, according to choice of $u,v$ there is written in the paper "either possibility contradicts our choice of u and v", looks like it's not true. I understand that the newest and more optimal C contradicts to initial condition 3. But conclusion was made with assumption that $|In(C)|\geq \frac{2n}{3}$ which is false, so conclusion also may be false, the things are a little mixed up there –  com Jan 24 '12 at 8:54
    
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. –  Willie Wong Jan 24 '12 at 9:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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