|
Description: |
> |
Many restricted crossing minimization problems are examined in the
literature. They either arise from special applications or from
heuristic simplifications of the general crossing number problem.
Many of these approaches lead to quadratic optimization problems in a
natural way.
In the so-called fixed linear crossing minimization problem all
nodes are placed on a horizontal line, in a fixed order, while edges
are drawn as semi-circles. The objective is to obtain a minimal number
of edge crossings. We showed that this problem is a special case of
the maximum cut problem in a certain auxiliary graph. Using a
branch-and-cut algorithm for the latter problem, we could solve much
larger instances to optimality than other approaches.
A similar problem is bipartite crossing minimization. Here, the
graph is bipartite and the aim is to
find a crossing-minimal bipartite
drawing, i.e., one in which the two
shores are drawn on two parallel
horizontal lines, while all edges are
drawn as straight lines. The number of
crossings thus depends on the chosen
order of nodes on the two shores. We
model this problem as a quadratic linear
ordering problem and show that the
corresponding polytope is a face of an
appropriate cut polytope. Exploiting
this polyhedral result both within an IP-
and an SDP-based algorithms, we can clearly
outperform other algorithms for
bipartite crossing minimization.
|
|
