An Experimental Study of Crossing Minimization Heuristics

Gutwenger, Carsten and Mutzel, Petra (2003) An Experimental Study of Crossing Minimization Heuristics. In: Graph Drawing 2003, 2003, Perugia . (In Press)

WarningThere is a more recent version of this item available.

[img] Other - Registered users only
102Kb

Abstract

We present an extensive experimental study of heuristics for crossing minimization. The heuristics are based on the planarization approach, so far the most successful framework for crossing minimization. We study the effects of various methods for computing a maximal planar subgraph and for edge re-insertion including post-processing and randomization.

Item Type:Conference Paper
Keywords:crossing minimization experimental planarization
Classifications:G Algorithms and Complexity > G.420 Crossings
M Methods > M.700 Planarization-based
ID Code:28

Available Versions of this Item

Repository Staff Only: item control page

References

Buchheim, Christoph and Jünger, Michael (2001) Detecting Symmetries by Branch & Cut . In Mutzel, Petra and Jünger, Michael and Leipert, Sebastian, Eds. Proceedings Graph Drawing, pages 178 -188, Wien.

Gutwenger, C. and Klein, K. and Kupke, J and Leipert, S. and Jünger, M. and Mutzel, P. (2002) Govisual software tools, http://www.oreas.de, 2002.

Gutwenger, C. and Mutzel, P. and Weiskircher, R. (2001) Inserting an edge into a planar graph. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '2001), pages 246--255, Washington, DC, 2001. ACM Press

Jayakumar, R. and Thulasiraman, K. and Swamy, M. N. S. (1989) O(n2) algorithms for graph planarization. In: IEEE Trans. on Computer-Aided Design, 8:257--267, 1989.

Johnson, M. R. and Johnson, D. S. (1983) Crossing number is {NP}-complete. In: SIAM J. Algebraic Discrete Methods, 4(3):312--316, 1983.

Jünger, M. and Leipert, S. and Mutzel, P. (1998) A note on computing a maximal planar subgraph using {PQ}-trees. In: IEEE Transactions on Computer-Aided Design, 17(7), 1998.

Jünger, M. and Mutzel P. (1996) Maximum planar subgraphs and nice embeddings: Practical layout tools. In: Algorithmica, Special Issue on Graph Drawing, 16(1):33--59

Jünger, M. and Mutzel, P. (1997) 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. In: Journal of Graph Algorithms and Applications (JGAA), 1(1):1--25