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 26: 03/30/2012

First, a restatement of the HW. I’ll update the post about HW 6 soon so look for that.

Today, we wrapped up the presentation of the polynomial-time planarity algorithm outlined in Wednesday’s lecture. It also gives hints about the linear-time algorithm and where the savings in time is.

The lemma is the main intuition behind why this works. Please study its proof and bring any questions to class (or ask them here)!

We’ll start the Planar Separator Theorem on Monday so please look over that section in Kozen.

Lecture 25: 03/28/2012

More Planarity.

We have a new HW assignment due next Wednesday. I’ll make a separate post for it.

How do we represent a planar graph? Well, I could tell you that a graph is planar, but that does you no good. I need to give you an embedding (without crossing edges), but how do I write it down?

We may represent an (unordered) edge as a pair of directed edges, one in each direction: e and e_

The _ operation reverses the direction of the edge, i.e., (e)_ = e_ and (e_)_ = e.

\theta is an orientation function of the edges around each vertex.

As we saw in the example in class, we can assign an orientation to every edge of a planar graph. It would be nice if we could show that this is possible only if the graph is planar. However, this isn’t true.

K_5 and K_(3,3) can be embedded, on some surfaces, just not the plane or a sphere. It is possible to embed them on a torus.

THM: Any graph can be embedded on some surface, i.e., sphere, torus, two-handled torus, etc.
COR: Any graph is locally planar.

How does a polynomial-time algorithm for embedding a graph work?
We’re given a graph G = (V, E). Start by finding a cycle in G. Find a path that cuts the cycle in half. At this point, we have three faces (two inner faces and the outside face).

Keep finding paths from the inside of a path to the inside of another path. Each time we insert a new path, we cut an existing face in two.

If we reach a point where the only paths left to insert are from a path to itself, we simply run the above procedure locally.

If at some point you can’t add a path without cutting across an edge, then the graph isn’t planar.

Study this algorithm and come up with some good questions for Friday’s lecture.

Lecture 24: 03/23/2012

Today’s topic is Planar Graphs.

We define a planar graph as a graph that can be embedded in the plane or a sphere, without any edges crossing.

How do you know if a graph is planar? Kuratowski’s theorem tells us that if a graph G is a subdivision of or contains K_5 (complete graph on 5 vertices) or K_(3,3) (complete bipartite graph on 3 vertices to 3 vertices) as a subgraph, then G is NOT planar.

That’s all well and good, but that doesn’t really give us an algorithm for finding an embedding. In CS, we like to actually give you a proof that it is planar, so what’s better than the embedding itself?

The Hopcroft-Tarjan algorithm produces an embedding in linear time. The original paper can be found here. It’s not a short paper so if anyone is interested, I can read it through and provide a good summary here on the blog.

We’ll wrap up the basic theory of planar graphs and get to the Planar Separator Theorem on Monday.

Enjoy the weekend!