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
83Kb

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
ID Code:23
Alternative Locations:http://e-archive.informatik.uni-koeln.de/203/

Available Versions of this Item

Repository Staff Only: item control page

References

CPLEX: Using the CPLEX callable library and the CPLEX mixed integer library. (1993), CPLEX Optimization Inc.

Dresbach, S. (1994) A New Heuristic Layout Algorithm for DAGs. Derigs, Bachem & Drexl (eds.) Operations Research Proceedings 1994, Springer Verlag, Berlin 121-126.

Dresbach, S. (1995) Personal communication.

Eades, P. and Kelly, D. (1986) Heuristics for Reducing Crossings in 2-Layered Networks. Ars Combinatoria 21-A 89-98.

Eades, P. and Wormald, N. C. (1994) Edge crossings in Drawings of Bipartite Graphs. Algorithmica 10 379-403.

Garey, M.R. and Johnson, D. S. (1983) Crossing Number is NP-Complete. SIAM J. on Algebraic and Discrete Methods 4 312-316.

Grötschel, M. and Jünger, M. and Reinelt, G. (1984) A cutting plane algorithm for the linear ordering problem. Operations Research 32 1195-1220.

Grötschel, M. and Jünger, M. and Reinelt, G. (1984) Optimal triangulation of large real world input-output matrices. Statistische Hefte 25 261-295 .

Grötschel, M. and Jünger, M. and Reinelt, G. (1985) Facets of the linear ordering polytope. Mathematical Programming 33 43-60.

Knuth, D.E. (1993) The Stanford GraphBase: A Platform for Combinatiorial Computing. ACM Press, Addison-Wesley Publishing Company, New-York.

Sugiyama, K. and Tagawa, S. and Toda, M. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, 11 109-125.

Warfield, J. N. (1977) Crossing Theory and Hierarchy Mapping. IEEE Trans. Syst., Man, Cybern., SMC-7 505-523.