2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms

Jünger, Michael and Mutzel, Petra (1996) 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms. [Preprint]

[img] Other
112Kb

Abstract

We present algorithms for the two 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 1997 by Brown University in the journal "Journal of Graph Algorithms and Applications", volume 1, pages 1-25.
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:22
Alternative Locations:http://e-archive.informatik.uni-koeln.de/243/

Repository Staff Only: item control page

References

Catarci, C. (1993) The Assignment Heuristic for Crossing Reduction. IEEE Transactions on Systems, Man, and Cybernetics. 25, No. 3.

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) 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.

Valls, V. and Marti, R. and Lino, P. (1996) A Branch and Bound Algorithm for Minimizing the Number of Crossing Arcs in Bipartite Graphs. Journal of Operational Research 90 303-319.

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