Layer-free upward crossing minimization

Abstract

An upward drawing of a DAG G is a drawing of G in which all arcs are drawn as curves increasing monotonically in the vertical direction. In this article, we present a new approach for upward crossing minimization, that is, finding an upward drawing of a DAG G with as few crossings as possible. Our algorithm is based on a two-stage upward planarization approach, which computes a feasible upward planar subgraph in the first step and reinserts the remaining arcs by computing constraint-feasible upward insertion paths. An experimental study shows that the new algorithm leads to much better results than existing algorithms for upward crossing minimization, including the classical Sugiyama approach.

References

1. Batini, C., Talamo, M., and Tamassia, R. 1984. Computer-aided layout of entity relationship diagrams. J. Syst. Software 4, 2--3, 163--173.
2. Battista, G. D., Eades, P., Tamassia, R., and Tollis, I. G. 1999. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River, NJ.
3. Bertolazzi, P., Battista, G. D., Liotta, G., and Mannino, C. 1994. Upward drawings of triconnected digraphs. Algorithmica 12, 6, 476--497.
4. Bertolazzi, P., Di Battista, G., Mannino, C., and Tamassia, R. 1998. Optimal upward planarity testing of single-source digraphs. SIAM J. Comput. 27, 1, 132--169.
5. Di Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., and Vismara, L. 2000. Drawing directed acyclic graphs: An experimental study. Int. J. Comput. Geom. Appl. 10, 6, 623--648.
6. Di Battista, G., Garg, A., Liotta, G., Tamassia, R., Tassinari, E., and Vargiu, F. 1997. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl. 7, 5-6, 303--325.
7. Dogrusoz, U., Duncan, C. A., Gutwenger, C., and Sander, G. 2008. Graph drawing contest report. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin.
8. Eiglsperger, M., Kaufmann, M., and Eppinger, F. 2003. An approach for mixed upward planarization. J. Graph Algorithms Appl. 7, 2, 203--220.
9. Eiglsperger, M., Siebenhaller, M., and Kaufmann, M. 2004. An efficient implementation of Sugiyama's algorithm for layered graph drawing. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin, 155--166.
10. Gansner, E., Koutsofios, E., North, S., and Vo, K.-P. 1993. A technique for drawing directed graphs. Softw. Pract. Exper. 19, 3, 214--229.
11. Garg, A. and Tamassia, R. 2001. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31, 2, 601--625.
12. Goldschmidt, O. and Takvorian, A. 1994. An efficient graph planarization two-phase heuristic. Networks 24, 2, 69--73.
13. Gutwenger, C. and Mutzel, P. 2004. An experimental study of crossing minimization heuristics. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin, 13--24.
14. OGDF. Open graph drawing framework. TU Dortmund, Chair of Algorithm Engineering; Version v.2007.11 (Bubinga). http://www.ogdf.net.
15. Siebenhaller, M. and Kaufmann, M. 2005. Mixed upward planarization -- fast and robust. In Proceedings of the Symposium on Graph Drawing. Springer, Berlin, 522--523.
16. Sugiyama, K., Tagawa, S., and Toda, M. 1981. Methods for visual understanding of hierarchical system structures. IEEE Trans. Sys. Man. Cyb. 11, 2, 109--125.

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Routing and network design problems