
6 CHAPTER 1. PLANARITY TESTING AND EMBEDDING
the planar embeddings of a given graph when searching for some embedding with a specific
property (see, for example, [MW99, MW00, BDBD00, GMW01, ADF
+
10]).
Given a plane (multi)graph G, its plane dual (or simply its dual) is the multigraph G
∗
such that G
∗
has one vertex for each face of G and two vertices of G
∗
are linked by one edge
e
∗
if t he corres ponding faces in G share one edge e. Observe that the planar embedding of
G induces a planar embedding of its dual and that the dual of the dual of G is G itself.
Also, different embeddings of a planar gr aph G correspond to different dual graphs. Finally,
a cycle ...