"Fixed Linear Crossing Minimization by Reduction to the Maximum Cut Problem"
Article by Christoph Buchheim, Lanbo Zheng, available as BibTeX Source and in portable document format.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2006-522
Keywords:	crossing minimization, max cut
MSC codes:	05C85
This article is to appear in "COCOON 2006".
Abstract:	Many real-life scheduling, routing and locating problems can be formulated as combinatorial optimization problems whose goal is to find a linear layout of an input graph in such a way that the number of edge crossings is minimized. In this paper, we study a restricted version of the linear layout problem where the order of vertices on the line is fixed, the so-called fixed linear crossing number problem (FLCNP). We show that this NP-hard problem can be reduced to the well-known maximum cut problem. The latter problem was intensively studied in the literature; practically efficient exact algorithms based on the branch-and-cut technique have been developed. By an experimental evaluation on a variety of graphs, we prove that using this reduction for solving FLCNP compares favorably to earlier branch-and-bound algorithms.