Lecture 28: 04/04/2012

Planar Separator Theorem.

Last time, we covered the main definitions associated with the statement of the theorem and today we dove into the proof/algorithm.

The algorithm is somewhat involved and consists of quite a few steps.

First, we need to embed the graph G in the plane (using our linear-time Hopcroft-Tarjan algorithm), otherwise it wouldn’t make sense to try and separate this graph in the plane.

We run a BFS traversal starting at an arbitrary vertex v and assign to each vertex its BFS level. We denote the vertices at the kth level by L(k). Since edges in a BFS traversal only go between vertices in the same level or adjacent levels, any such set L(k) is actually a separator.

We’ll look at level t_1, which is the “middle” level, i.e., the one containing the (n/2)th vertex in the traversal. If the size of L(t_1) is at most 4 sqrt(n), then we’re done, since it separates the graph into two components, A and B, where each is the set of vertices in levels before and after t_1, respectively. We also know that each of these has at most n/2 vertices.

Alas, this isn’t always the case in algorithms. So what if L(t_1) is too big? We’ll find levels t_0 t_1 as close as possible to t_1 so that the size of L(t_0) and L(t_2) is no bigger than sqrt(n).

What do these give us? We now have three partitions of the BFS tree into C, D, and E of vertices before t_0, between t_0 and t_2, and after t_2, respectively.

If the size of D is at most 2n/3, then we’re done. Why?

Say D has at least n/3 vertices, then the other two sets have at most 2n/3 vertices among them, so we take A = D and B to be the union of C and E. The separator in this case is just the disjoint union of L(t_0) and L(t_2).

If D has less than n/3 vertices, then one of the other two sets must have at least n/3 – O(sqrt(n)) vertices, otherwise we violate the law of conservation of mass and lose some vertices. WLOG, say this set is C, then we let A = C and B is the union of D and E.

Are we done yet?? We still need to consider the case that D is bigger than 2n/3. At least it shrunk by a little bit, so as we noted in lecture, we could just recurse and build A, B, and S that way.

Another way to deal with D is to split it “in half” once and be done with it.

We’ll finish up the proof on Friday. Study the cases well and bring any questions to class or ask them here.

Advertisements

Lecture 27: 04/02/2012

Today’s topic: The Planar Separator Theorem.

What does it say? A planar graph on n vertices has a small “separator,” meaning we can partition the set of vertices into three sets A, B, and S such that:
1) |A|, |B| <= 2n/3
2) |S| <= 4 sqrt{n}
3) There is no edge between A and B.

We started the proof of the theorem today and solved the first few cases. If the graph is already disconnected, and the components are small enough, there isn't much to do.

If one of the components is too big, or if the graph itself is connected, we actually have to find a separator set. The process of finding such a separator starts with a BFS traversal and labeling of the levels.

Please review the boards and the book before Wednesday's class. We'll finish up the theorem next time so bring all of your questions (or ask them here)!

We also have a small correction to the homework assignment which I will correct in its own post.