
2.3. COMPLEXITY OF CROSSING MINIMIZATION 53
u
w
Figure 2.6 Reducing the bipartite crossing number problem to the general crossing num-
ber problem for multigraphs. Bold grey lines represent bundles of K + 1 edges each.
with other edges. Then one can reroute all edges (u, v), i.e., all edges parallel to e, along
the same route as e. This yields a new drawing of G
′
with at most as many edge crossings
as before. Repeating this for e very v ∈ V
1
and analogously f or w and every v ∈ V
2
, we get
a drawing without vertices in the bundle regions. Now it follows that no edge can cross
any of these regions. The reason is that such an edge would have to cross all ...