2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
Michael Jünger, Petra Mutzel · Journal of Graph Algorithms and Applications · 1997
We present algorithms for the twolayer 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 #xed, even though the problem is NP-hard, and that for the general problem with twovariable 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 their results to optimum solutions. Communicated byP. Eades: submitted August 1996; revised November 1996. Research supported in part byDFG-Grant Ju204#7-1, Forschungsschwerpunkt #Ef- #ziente Algorithmen f#ur diskrete Probleme und ihre Anwendungen" and by ESPRIT LTR Project no. 20244 # ALCOM-IT M. J#unger et al., 2-Layer Crossing Minimization, JGAA, 1#1# 1#25 #1997# 2 1 Introduction Direc...