Mathematics for Computer Science

12.2. Definitions of Planar Graphs 369

y

w

a

z

b

x

Figure 12.9 The “split a face” case:awxbyzasplits intoawxybaandabyza.

z

b

t

v

a

x

y

u

w

Figure 12.10 The “add a bridge” case.

This is illustrated in Figure 12.10, where the vertex sequences of the faces ofG
andHare:

GWfaxyza; axya; ayzag HWfbtuvwb; btvwb; tuvtg;

and after adding the bridgeha—bi, there is a single connected graph whose faces
have the vertex sequences

faxyzabtuvwba; axya; ayza; btvwb; tuvtg:

12.2.3 Does It Work?

Yes! In general, a graph is planar if and only if each of its connected components
has a planar embedding as defined in Definition 12.2.2. Unfortunately, proving
this fact requires a some continuous mathematics known as elementary point/set
topology that we don’t cover in this. Of course, that is why we went to the trouble
of including Definition 12.2.2 —we don’t want to deal with the continuous stuff in