Exact Crossing Minimization

Buchheim, Christoph and Ebner, Dietmar and Jünger, Michael and Klau, Gunnar W. and Mutzel, Petra and Weiskircher, René (2006) Exact Crossing Minimization. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 37-48(Official URL: http://dx.doi.org/10.1007/11618058_4).

Full text not available from this repository.


The crossing number of a graph is the minimum number of edge crossings in any drawing of the graph into the plane. This very basic property has been studied extensively in the literature from a theoretic point of view and many bounds exist for a variety of graph classes. In this paper, we present the first algorithm able to compute the crossing number of general sparse graphs of moderate size and present computational results on a popular benchmark set of graphs. The approach uses a new integer linear programming formulation of the problem combined with strong heuristics and problem reduction techniques. This enables us to compute the crossing number for 91 percent of all graphs on up to 40 nodes in the benchmark set within a time limit of five minutes per graph.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_4
Classifications: G Algorithms and Complexity > G.420 Crossings
URI: http://gdea.informatik.uni-koeln.de/id/eprint/678

Actions (login required)

View Item View Item