Chapter 12 Planar Graphs368
12.2.2 A Recursive Definition for Planar Embeddings
The association between the continuous faces of a planar drawing and closed walks
will allow us to characterize a planar drawing in terms of the closed walks that
bound the continuous faces. In particular, it leads us to the discrete data type ofpla-
nar embeddingsthat we can use in place of continuous planar drawings. We’ll de-
fine a planar embedding recursively to be the set of boundary-tracing closed walks
that we could get by drawing one edge after another.
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.
Constructor case(split a face): SupposeGis a connected graph with a planar
embedding, and supposeaandbare distinct, nonadjacent vertices ofGthat occur
in some discrete face, , of the planar embedding. That is, is a closed walk of the
form
̨bb ˇ
where ̨is a walk fromatobandˇis a walk frombtoa. Then the graph obtained
by adding the edgeha—bito the edges ofGhas a planar embedding with the same
discrete faces asG, except that face is replaced by the two discrete faces^3
̨bhb—ai and ha—bibˇas illustrated in Figure 12.9.
Constructor case(add a bridge): SupposeGandH are connected graphs with
planar embeddings and disjoint sets of vertices. Let be a discrete face of the
embedding ofGand suppose that begins and ends at vertexa.
Similarly, letıbe a discrete face of the embedding ofHthat begins and ends at
vertexb.
Then the graph obtained by connectingGandHwith a new edge,ha—bi, has a
planar embedding whose discrete faces are the union of the discrete faces ofGand
H, except that faces andıare replaced by one new face
b.aha—bib/bıb.bhb—aia/:(^3) There is a minor exception to this definition of embedding in the special case whenGis a line
graph beginning withaand ending withb. In this case the cycles into which splits are actually
the same. That’s because adding edgeha—bicreates a cycle that divides the plane into “inner” and
“outer” continuous faces that are both bordered by this cycle. In order to maintain the correspondence
between continuous faces and discrete faces in this case, we define the two discrete faces of the
embedding to be two “copies” of this same cycle.