Chapter 12 Planar Graphs366
II I
III
IV
Figure 12.5 A planar drawing with four continuous faces.dcba II IIII
IV
Figure 12.6 The drawing with labeled vertices.discrete facesof the graph in Figure 12.6. We use the term “discrete” since cycles
in a graph are a discrete data type —as opposed to a region in the plane, which is a
continuous data type.
Unfortunately, continuous faces in planar drawings are not always bounded by
cycles in the graph —things can get a little more complicated. For example, the
planar drawing in Figure 12.7 has what we will call abridge, namely, the edge
hc—ei. The sequence of vertices along the boundary of the outer region of the
drawing is
abcefgecda:
This sequence defines a closed walk, but does not define a cycle since the walk has
two occurrences of the bridgehc—eiand each of its endpoints.
The planar drawing in Figure 12.8 illustrates another complication. This drawing
has what we will call adongle, namely, the nodesv,x,y, andw, and the edges
incident to them. The sequence of vertices along the boundary of the inner region