Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization

Jünger, Michael and Mutzel, Petra (1995) Exact and Heuristic Algorithms for 2-Layer Straightline Crossing Minimization. [Preprint]

WarningThere is a more recent version of this item available.
[img] Other
Download (85kB)

Abstract

We present algorithms for the 2-layer straightline crossing minimization problem that are able to compute exact optima. Our computational results lead us to the conclusion that there is no need for heuristics if one layer is fixed, even though the problem is NP-hard, and that for the general problem with two variable layers, true optima can be computed for sparse instances in which the smaller layer contains up to 15 nodes. For bigger instances, the iterated barycenter method turns out to be the method of choice among several popular heuristics whose performance we could assess by comparing the results to optimum solutions.

Item Type: Preprint
Additional Information: This article was published in 1996 by Springer in the proceedings "Proc. Symposium on Graph Drawing '95" (edited by F. Brandenburg), series "Lecture Notes in Computer Science", pages 337-348.
Classifications: P Styles > P.720 Straight-line
G Algorithms and Complexity > G.420 Crossings
M Methods > M.500 Layered
P Styles > P.480 Layered
URI: http://gdea.informatik.uni-koeln.de/id/eprint/23

Available Versions of this Item

Actions (login required)

View Item View Item