Mathematics for Computer Science

12.2. Definitions of Planar Graphs 367

b

e

f

g

c

d

a

Figure 12.7 A planar drawing with abridge.

s

t

u

r

v

x

y

w

Figure 12.8 A planar drawing with adongle.

is
rstvxyxvwvtur:

This sequence defines a closed walk, but once again does not define a cycle because
it has two occurrences ofeveryedge of the dongle —once “coming” and once
“going.”
It turns out that bridges and dongles are the only complications, at least for con-
nected graphs. In particular, every continuous face in a planar drawing corresponds
to a closed walk in the graph. These closed walks will be called thediscrete faces
of the drawing, and we’ll define them next.