"A New Exact Algorithm for the Two-Sided Crossing Minimization Problem"
Article by Lanbo Zheng, Christoph Buchheim, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2007-540
Keywords:	crossing minimization, quadratic binary programming
MSC codes:	68R10, 90C20
This article is to appear in "COCOA 2007".
Abstract:	The Two-Sided Crossing Minimization (TSCM) problem calls for minimizing the number of edge crossings of a bipartite graph where the two sets of vertices are drawn on two parallel layers and edges are drawn as straight lines. This well-known problem has important applications in VLSI design and automatic graph drawing. In this paper, we present a new branch-and-cut algorithm for the TSCM problem by modeling it directly to a binary quadratic programming problem. We show that a large number of effective cutting planes can be derived based on a reformulation of the TSCM problem. We compare our algorithm with a previous exact algorithm by testing both implementations with the same set of instances. Experimental evaluation demonstrates the effectiveness of our approach.