1.  Planar Graph

• G = (V,E)

S Í V is an f(n) seperator if:

1. |S| £ f(n)
2. $ partition A,B of V-S with |A|,|B| £ ²/₃n
3. no edge from A to B

2.  Planar Seperator Theorem

Actually, the current bound is 1.8Ön .

Assume G is planar, embedded and triangulated.

For some s Î V do a BFS from s . The BFS tree constructed induces natural partitions in the graph. Consider A = all nodes within depth d and B = all nodes which are more than depth d away.

Define:

• level(s) = 0
• L(t) = set of vertices at level t
• A_t = È_{i < t}L(i)
• S_t = L(t)
• B_t = È_{i > t}L(i)

In general, the BFS method won't necessarily produce a linear seperator. Let t = min_t|B_t| £ ⁿ/₂ .

Then |B_t-1| > ⁿ/₂ with B_t-1 = S_tÈB_t so A_t < ⁿ/₂

|S| may still be too large.

Let t₀ = max_{t¢ < t}|L(t)| £ Ön and let t₁ = min_{t¢ > t}|L(t)| £ Ön

It must be that t₁-t₀ £ Ön or else you would have more than Ön points.

Now you can make cuts at t₁ and t₀ , which gets you part way. The rest of the proof is less rigorous. The basic idea is to construct G¢ = (V¢,E¢) from the interior portion of the graph betwen t₁ and t₀ . V¢ = È_{t0 < t¢ < t1}L(t¢)È{s} .

Let T = spanning tree of G¢. diameter(T) £ 2Ön

• e = non-tree edge with C_e the cycle induced by adding e to the spanning tree.
• I(e) = # vertices interior to C_e
• O(e) = # vertices exterior to C_e

'interior' and 'exterior' are well defined because the graph is embedded in the plane.

Assume you have picked some e . Then either we are done, or without loss of generality, assume the interior is too big. The interior face that e is part of has several possibilities:

1. interior = face (both edges in spanning tree) we must be done.
2. 1 edge in the spanning tree and in cycle. Recurse with e = other interior edge.
3. 1 edge in the spanning tree but not in the cycle. Recurse with e = other interior edge.
4. no edges in spanning tree. Recurse with e = one of the interior edges.

The interior will always shrink during this recursion so the only question is whether or not the exterior gets too large too fast. The hard case is (4). None of the edges are in the spanning tree and |interior| > ²/₃n . We have a choice of between which 2 edges of the interior face to recurse on. Choose the interior edge which will leave the largest interior. Then the exterior can't become greater than ²/₃ in the recursion.

Combining this theorem with the fact that diameter(T) £ 2Ön allows us to make a cut of size 2Ön s.t., the nodes are divided into 2 large sets.