research-article

Layer-free upward crossing minimization

Authors:

Markus Chimani,

Carsten Gutwenger,

Hoi-Ming WongAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 15

Article No.: 2.2, Pages 2.1 - 2.27

https://doi.org/10.1145/1671970.1671975

Published: 17 March 2010 Publication History

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.

Digital Library

[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.

Digital Library

[3]

Bertolazzi, P., Battista, G. D., Liotta, G., and Mannino, C. 1994. Upward drawings of triconnected digraphs. Algorithmica 12, 6, 476--497.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[11]

Garg, A. and Tamassia, R. 2001. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31, 2, 601--625.

Digital Library

[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.

Digital Library

[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.

Cited By

Di Bartolomeo SCrnovrsanin TSaffo DPuerta EWilson CDunne C(2024)Evaluating Graph Layout Algorithms: A Systematic Review of Methods and Best PracticesComputer Graphics Forum10.1111/cgf.1507343:6Online publication date: 3-May-2024
https://doi.org/10.1111/cgf.15073
Didimo WKornaropoulos EMontecchiani FTollis I(2017)A Visualization Framework and User Studies for Overloaded Orthogonal DrawingsComputer Graphics Forum10.1111/cgf.1326637:1(288-300)Online publication date: Sep-2017
https://doi.org/10.1111/cgf.13266
Chimani MZeranski R(2015)Upward Planarity Testing in PracticeACM Journal of Experimental Algorithmics10.1145/269987520(1-27)Online publication date: 22-Apr-2015
https://dl.acm.org/doi/10.1145/2699875
Show More Cited By

Index Terms

Layer-free upward crossing minimization
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Layer-free upward crossing minimization
WEA'08: Proceedings of the 7th international conference on Experimental algorithms

An upward drawing of a DAG G is a drawing of G in which all edges are drawn as curves increasing monotonically in the vertical direction. In this paper, we present a new approach for upward crossing minimization, i.e., finding an upward drawing of a DAG ...
Volume requirements of 3D upward drawings

This paper studies the problem of drawing directed acyclic graphs in three dimensions in the straight-line grid model so that all directed edges are oriented in a common (upward) direction. We show that there exists a family of outerplanar directed ...
Optimal Upward Planarity Testing of Single-Source Digraphs

A digraph is upward planar if it has a planar drawing such that all the edges are monotone with respect to the vertical direction. Testing upward planarity and constructing upward planar drawings is important for displaying hierarchical network ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 15, Issue

2010

387 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/1671970

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 March 2010

Accepted: 01 November 2009

Revised: 01 October 2009

Received: 01 December 2008

Published in JEA Volume 15

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

priority project (SPP)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
452
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Di Bartolomeo SCrnovrsanin TSaffo DPuerta EWilson CDunne C(2024)Evaluating Graph Layout Algorithms: A Systematic Review of Methods and Best PracticesComputer Graphics Forum10.1111/cgf.1507343:6Online publication date: 3-May-2024
https://doi.org/10.1111/cgf.15073
Didimo WKornaropoulos EMontecchiani FTollis I(2017)A Visualization Framework and User Studies for Overloaded Orthogonal DrawingsComputer Graphics Forum10.1111/cgf.1326637:1(288-300)Online publication date: Sep-2017
https://doi.org/10.1111/cgf.13266
Chimani MZeranski R(2015)Upward Planarity Testing in PracticeACM Journal of Experimental Algorithmics10.1145/269987520(1-27)Online publication date: 22-Apr-2015
https://dl.acm.org/doi/10.1145/2699875
Binucci CDidimo W(2015)Computing Quasi-Upward Planar Drawings of Mixed GraphsThe Computer Journal10.1093/comjnl/bxv082(bxv082)Online publication date: 8-Oct-2015
https://doi.org/10.1093/comjnl/bxv082
Di Giacomo ELiotta GTamassia R(2013)Drawings of GraphsHandbook of Graph Theory, Second Edition10.1201/b16132-73(1239-1290)Online publication date: 26-Nov-2013
https://doi.org/10.1201/b16132-73
Bachmaier CBrunner WGleißner A(2012)Grid siftingJournal of Experimental Algorithmics (JEA)10.1145/2133803.234568217(1.1-1.23)Online publication date: 16-Oct-2012
https://dl.acm.org/doi/10.1145/2133803.2345682
Chimani MHungerländer PJünger MMutzel P(2012)An SDP approach to multi-level crossing minimizationJournal of Experimental Algorithmics (JEA)10.1145/2133803.233008417(3.1-3.26)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2133803.2330084
Widanagamaachchi WChristensen CBremer PPascucci V(2012)Interactive exploration of large-scale time-varying data using dynamic tracking graphsIEEE Symposium on Large Data Analysis and Visualization (LDAV)10.1109/LDAV.2012.6378962(9-17)Online publication date: Oct-2012
https://doi.org/10.1109/LDAV.2012.6378962
Chimani MZeranski R(2012)Upward planarity testing via SATProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_22(248-259)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_22
Betz GDoll CGemsa ARutter IWagner D(2012)Column-Based graph layoutsProceedings of the 20th international conference on Graph Drawing10.1007/978-3-642-36763-2_21(236-247)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-36763-2_21
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents