An Experimental Study of Crossing Minimization Heuristics

Gutwenger, Carsten and Mutzel, Petra (2004) An Experimental Study of Crossing Minimization Heuristics. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_2).

This is the latest version of this item.

Full text not available from this repository.

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
Additional Information:10.1007/978-3-540-24595-7_2
Classifications:G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.420 Crossings
ID Code:407

Available Versions of this Item

Repository Staff Only: item control page

References

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956-997, 1996.

S. N. Bhatt and F. T. Leighton. A framework for solving VLSI layout problems. Journal of Computer and System Sciences, 28:300-343, 1984.

D. Bienstock. Some provably hard crossing number problems. Discrete & Computational Geometry, 6:443-459, 1991.

F. J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F. J. Brandenburg, editor, GD '95, volume 1027 of LNCS, pages 76-87. Springer-Verlag, 1996.

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Comput. Syst. Sci., 30(1):54-76, 1985.

G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303-326, 1997.

T. Eschbach, W. Günther, R. Drechsler, and B. Becker. Crossing reduction by windows optimization. In M. T. Goodrich and S. G. Kobourov, editors, Graph Drawing '02, volume 2528 of LNCS, pages 285-294. Springer-Verlag, 2002.

G. Even, S. Guha, and B. Schieber. Improved approximations of crossings in graph drawing and VLSI layout area. In Proc. 32nd ACM Symp. Theory of Comp. (STOC '00), pages 296-305. ACM Press, 2000.

M. Grohe. Computing crossing numbers in quadratic time. In Proc. 32nd ACM Symp. Theory of Computing (STOC '00), pages 231-236. ACM Press, 2000.

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

C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. In Proc. Ninth Ann. ACM-SIAM Symp. Discr. Algorithms (SODA '2001), pages 246-255, Washington, DC, 2001. ACM Press.

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

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

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

M. Jünger and P. Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algoritmica 16(1):33-59, 1996.

M. Jünger and P. Mutzel. 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. J. Gr. Alg. & Appl., (JGAA), 1(1):1-25, 1997.

F. T. Leighton and S. Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM, 46(6):787-832, 1999.

P. C. Liu and R. C. Geldmacher. On the deletion of nonplanar edges of a graph. In 10th. S-E Conf. Comb., Graph Theory, and Comp., pages 727-738, 1977.

K. Mehlhorn and P. Mutzel. On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. Algorithmica, 16(2):233-242, 1996.

P. Mutzel and T. Ziegler. The constrained crossing min. problem. In J. Kratochvíl, editor, GD '99, volume 1731 of LNCS, pages 175-185. Springer-Verlag, 1999.

J. A. La Poutré. Alpha-algorithms for incremental planarity testing. In Proc. 26th Annual ACM Symp. Theory of Computation (STOC), pages 706-715, 1994.

H. Purchase. Which aesthetic has the greatest effect on human understanding? In G. Di Battista, editor, Graph Drawing '97, volume 1353 of LNCS, pages 248-261. Springer-Verlag, 1997.

R. B. Richter and C. Thomassen. Relations between crossing numbers of complete and complete bipartite graphs. Amer. Math. Monthly, pages 131-137, 1997.

L. Vismara, G. Di Battista, A. Garg, G. Liotta, R. Tamassia, and F. Vargiu. Experimental studies on graph drawing algorithms. Software - Practice and Experience, 30:1235-1284, 2000.

T. Ziegler. Crossing Minimization in Automatic Graph Drawing. PhD thesis, Max-Planck-Institut für Informatik, Saarbrücken, 2000.