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!