We present an approach based on semidefinite programs (SDP) to tackle the
multi-level crossing minimization problem. Thereby, we are given a layered graph
(i.e., the graph's vertices are assigned to multiple parallel levels) and ask
for an ordering of the nodes on their levels such that, when drawing the graph
with straight lines, the resulting number of crossings is minimized. Solving
this step is crucial in the probably most widely used graph drawing scheme, the
so-called Sugiyama framework.
The problem has received a lot of attention both in the field of heuristics and
exact methods. For a long time, integer linear programming (ILP) approaches were
the only exact algorithms applicable at least to small graphs. Recently, SDP
formulations for the special case of two levels were proposed and dominated the
ILP for dense instances.
In this paper, we present a new SDP formulation for the general multi-level
version that, for two-levels, is even stronger than the aforementioned
specialized SDP. As a side-product, we also obtain an SDP-based heuristic which
in practice always gives (near-)optimal solutions.
We conduct a large set of experiments, both on randomized and on real-world
instances, and compare our approach to a state-of-the-art ILP-based
branch-and-cut implementation. The SDP clearly dominates for denser graphs,
while the ILP approach is usually faster for sparse instances. However, even for
such sparse graphs, the SDP solves more instances to optimality than the ILP. In
fact, there is no single instance the ILP solved, which the SDP did not.
Overall, our experiments reveal that for sparse graphs, one should usually try
to find an optimal solution with the ILP first. If this approach does not solve
the instance to optimality within reasonable time, the SDP still has a good
chance to do so.
Being able to solve larger real-world instances than reported before, we are
also able to evaluate heuristics for this problem. In this paper we do so for
the traditional barycenter-heuristic (showing that it leaves a large gap to the
true optimum) and the state-of-the-art upward-planarization method (showing that
it is usually close to the optimum). |