"Exact Crossing Minimization"
Article by Christoph Buchheim, Dietmar Ebner, Michael Jünger, Gunnar W. Klau, Petra Mutzel, René Weiskircher, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2005-502
Keywords:	crossing minimization, graph drawing
MSC codes:	05C85, 90C57
This article is to appear in "Graph Drawing 2005".
Abstract:	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.