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.