Chapter 12 Planar Graphs480
sturvxywFigure 12.8 A planar drawing with adongle.vertices —not what a drawing of the graph actually looks like —planar embeddings
are exactly what we need.
The question is how to define planar embeddings without appealing to continu-
ous drawings. There is a simple way to do this based on the idea that any continuous
drawing can drawn step by step:
either draw a new point somewhere in the plane to represent a vertex, or draw a curve between two vertex points that have already been laid down,
making sure the new curve doesn’t cross any of the previously drawn curves.A new curve won’t cross any other curves precisely when it stays within one
of the continuous faces. Alternatively, a new curve won’t have to cross any other
curves if it can go between the outer faces of two different drawings. So to be sure
it’s ok to draw a new curve, we just need to check that its endpoints are on the
boundary of the same face, or that its endpoints are on the outer faces of different
drawings. Of course drawing the new curve changes the faces slightly, so the face
boundaries will have to be updated once the new curve is drawn. This is the idea
behind the following recursive definition.
Definition 12.2.2.Aplanar embeddingof aconnectedgraph consists of a nonempty
set of closed walks of the graph called thediscrete facesof the embedding. Planar
embeddings are defined recursively as follows:
Base case: IfGis a graph consisting of a single vertex,v, then a planar embedding
ofGhas one discrete face, namely, the length zero closed walk,v.