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.
Published In: Graph drawing : 13th international symposium, GD 2005, Limerick, Ireland, September 12 - 14, 2005 ; revised papers, Lecture Notes in Computer Science. 3843 Springer 2006, pp. 37-48.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2005-502
Depositing User: Christoph Buchheim
Date Deposited: 01 Dec 2005 00:00
Last Modified: 08 Jul 2013 08:30
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/502