Abstract
The one-sided two-level crossing reduction problem is an important problem in hierarchical graph drawing. Because of its NP-hardness there are many heuristics, such as the well-known barycenter and median heuristics. We consider the constrained one-sided two-level crossing reduction problem, where the relative position of certain vertex pairs on the second level is fixed. Based on the barycenter heuristic, we present a new algorithm that runs in quadratic time and generates fewer crossings than existing simple extensions. It is significantly faster than an advanced algorithm by Schreiber [12] and Finnocchi [1,2,6], while it compares well in terms of crossing number. It is also easy to implement.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Demetrescu, C., Finocchi, I.: Break the “right” cycles and get the “best” drawing. In: Moret, B., Goldberg, A. (eds.) Proc. ALENEX 2000, pp. 171–182 (2000)
Demetrescu, C., Finocchi, I.: Removing cycles for minimizing crossings. ACM Journal on Experimental Algorithmics (JEA) 6(1) (2001)
di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Englewood Cliffs (1999)
Eades, P., McKay, B.D., Wormald, N.C.: On an edge crossing problem. In: Proc. ACSC 1986, Australian National University, pp. 327–334 (1986)
Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica 11, 379–403 (1994)
Finocchi, I.: Layered drawings of graphs with crossing constraints. In: Wang, J. (ed.) COCOON 2001. LNCS, vol. 2108, pp. 357–368. Springer, Heidelberg (2001)
Forster, M.: Applying crossing reduction strategies to layered compound graphs. In: Kobourov, S.G., Goodrich, M.T. (eds.) GD 2002. LNCS, vol. 2528, pp. 276–284. Springer, Heidelberg (2002)
Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316 (1983)
Jünger, M., Mutzel, P.: Exact and heuristic algorithms for 2-layer straightline crossing minimization. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 337–348. Springer, Heidelberg (1996)
Jünger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performance of exact and heuristic algorithms. JGAA 1(1), 1–25 (1997)
Sander, G.: Visualisierungstechniken für den Compilerbau. PhD thesis, University of Saarbrücken (1996)
Schreiber, F.: Visualisierung biochemischer Reaktionsnetze. PhD thesis, University of Passau (2001)
Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. SMC 11(2), 109–125 (1981)
Waddle, V.: Graph layout for displaying data structures. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 241–252. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Forster, M. (2005). A Fast and Simple Heuristic for Constrained Two-Level Crossing Reduction. In: Pach, J. (eds) Graph Drawing. GD 2004. Lecture Notes in Computer Science, vol 3383. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31843-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-31843-9_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24528-5
Online ISBN: 978-3-540-31843-9
eBook Packages: Computer ScienceComputer Science (R0)