A New Exact Algorithm for the Two-Sided Crossing Minimization Problem

Zheng, Lanbo and Buchheim, Christoph (2007) A New Exact Algorithm for the Two-Sided Crossing Minimization Problem.
Published In: Combinatorial optimization and applications first international conference, COCOA 2007, Xi'an, China, August 14-16, 2007 ; proceedings, Lecture Notes in Computer Science. 4616 Springer 2007, pp. 301-310.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2007-540
Depositing User: Christoph Buchheim
Date Deposited: 03 May 2007 00:00
Last Modified: 11 Aug 2011 14:40
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/540