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!