R. Martí and M. Laguna
Discrete Applied Mathematics, vol. 127, no. 3, pp. 665-678 (2003)
This paper presents extensive computational experiments to compare 12 heuristics and 2 meta-heuristics for the problem of minimizing straight line crossings in a 2-layer graph. These experiments show that the performance of the heuristics (largely based on simple ordering rules) drastically deteriorates as the graphs become sparser. A tabu search metaheuristic yields the best results for relatively dense graphs, with a GRASP implementation as close second. The GRASP approach, on the other hand, outperforms all other approaches when tackling low-density graphs.
Full text
