
58 CHAPTER 2. CROSSINGS AND PLANARIZATION
a
b
c d
e
f
g
h
i
j
k
l
m
n
o
p
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
Figure 2.8 An optimal drawing of a graph with two crossings (left) and an optimal simple
drawing of the same graph with three crossings (right). Both drawings were produced with
the exact algorithm presented in this section.
u v
u v
d
1
d
2
d
l-1
d
l-2
Figure 2.9 Edges are replaced with a path of le ngth ℓ by inserting ℓ −1 dummy vertices.
Given an integer ℓ and a graph G = (V, E) such that ℓ ≥ |E|, we can create a graph
G
∗
= (V
∗
, E
∗
) by replacing every edge e ∈ E with a path of length ℓ. Figure 2.9 sh ows
an example that illustrates this transformation. The graph G
∗
contains a total