Article

Stress-Plus-X (SPX) Graph Layout

Authors:

Felice De Luca,

Katherine E. Isaacs,

Stephen KobourovAuthors Info & Claims

Graph Drawing and Network Visualization: 27th International Symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019, Proceedings

Pages 291 - 304

https://doi.org/10.1007/978-3-030-35802-0_23

Published: 17 September 2019 Publication History

Abstract

Stress, edge crossings, and crossing angles play an important role in the quality and readability of graph drawings. Most standard graph drawing algorithms optimize one of these criteria which may lead to layouts that are deficient in other criteria. We introduce an optimization framework, Stress-Plus-X (SPX), that simultaneously optimizes stress together with several other criteria: edge crossings, minimum crossing angle, and upwardness (for directed acyclic graphs). SPX achieves results that are close to the state-of-the-art algorithms that optimize these metrics individually. SPX is flexible and extensible and can optimize a subset or all of these criteria simultaneously. Our experimental analysis shows that our joint optimization approach is successful in drawing graphs with good performance across readability criteria.

References

[1]

Ábrego BM, Fernández-Merchant S, and Salazar G The rectilinear crossing number of

k_{n}

: closing in (or are we?) Thirty Essays Geom. Gr. Theory 2012

[2]

Argyriou EN, Bekos MA, and Symvonis A Brandes U and Cornelsen S Maximizing the total resolution of graphs Graph Drawing 2011 Heidelberg Springer 62-67

[3]

Bekos, M.A., Förster, H., Geckeler, C., Holländer, L., Kaufmann, M., Spallek, A.M., Splett, J.: A heuristic approach towards drawings of graphs with high crossing resolution. CoRR abs/1808.10519 (2018). http://arxiv.org/abs/1808.10519

[4]

Buchheim, C., Chimani, M., Gutwenger, C., Jünger, M., Mutzel, P.: Crossings and planarization. In: Handbook of Graph Drawing and Visualization, pp. 43–85 (2013)

[5]

Chen L and Buja A Local multidimensional scaling for nonlinear dimension reduction, graph drawing, and proximity analysis J. Am. Stat. Assoc. 2009 104 485 209-219

[6]

Dagrejs: dagrejs/dagre. https://github.com/dagrejs/dagre/wiki

[7]

De Luca, F.: graphmetrics library (2019). https://github.com/felicedeluca/graphmetrics

[8]

Demel A, Dürrschnabel D, Mchedlidze T, Radermacher M, and Wulf L Biedl T and Kerren A A greedy heuristic for crossing-angle maximization Graph Drawing and Network Visualization 2018 Cham Springer 286-299

[9]

Devanny W, Kindermann P, Löffler M, and Rutter I Frati F and Ma K-L Graph drawing contest report Graph Drawing and Network Visualization 2018 Cham Springer 575-582

[10]

Devanny W, Kindermann P, Löffler M, and Rutter I Biedl T and Kerren A Graph drawing contest report Graph Drawing and Network Visualization 2018 Cham Springer 609-617

[11]

Devkota, S., Ahmed, R., De Luca, F., Isaacs, K., Kobourov, S.: Stress-Plus-X (SPX) graph layout (2019)

[12]

Duncan CA, Gutwenger C, Nachmanson L, and Sander G Didimo W and Patrignani M Graph drawing contest report Graph Drawing 2013 Heidelberg Springer 575-579

[13]

Dwyer T Scalable, versatile and simple constrained graph layout Comput. Graph. Forum 2009 28 991-998

[14]

Dwyer T, Koren Y, and Marriott K Ipsep-cola: an incremental procedure for separation constraint layout of graphs IEEE Trans. Vis. Comput. Gr. 2006 12 821-828

[15]

Ellson J, Gansner E, Koutsofios L, North SC, and Woodhull G Mutzel P, Jünger M, and Leipert S Graphviz— open source graph drawing tools Graph Drawing 2002 Heidelberg Springer 483-484

[16]

Fruchterman TMJ and Reingold EM Graph drawing by force-directed placement Softw. Pract. Exp. 1991 21 11 1129-1164

[17]

Gansner ER, Koren Y, and North S Pach J Graph drawing by stress majorization Graph Drawing 2005 Heidelberg Springer 239-250

[18]

Gansner, E.R., North, S.C., Vo, K.P.: Technique for drawing directed graphs (1990). uS Patent 4,953,106

[19]

Gutwenger C, Löffler M, Nachmanson L, and Rutter I Duncan C and Symvonis A Graph drawing contest report Graph Drawing 2014 Heidelberg Springer 501-506

[20]

Huang W, Eades P, and Hong SH Larger crossing angles make graphs easier to read J. Vis. Lang. Comput. 2014 25 4 452-465

[21]

Huang W, Eades P, Hong SH, and Lin CC Improving multiple aesthetics produces better graph drawings J. Vis. Lang. Comput. 2013 24 4 262-272 http://www.sciencedirect.com/science/article/pii/S1045926X11000814

[22]

Kamada T and Kawai S An algorithm for drawing general undirected graphs Inf. Process. Lett. 1989 31 1 7-15 http://www.sciencedirect.com/science/article/pii/0020019089901026

[23]

Kruiger JF, Rauber PE, Martins RM, Kerren A, Kobourov S, and Telea AC Graph layouts by t-sne Comput. Graph. Forum 2017 36 3 283-294

[24]

Kruskal JB Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis Psychometrika 1964 29 1 1-27

[25]

Maaten LVD and Hinton G Visualizing data using t-sne J. Mach. Learn. Res. 2008 9 Nov 2579-2605

[26]

McInnes, L., Healy, J., Melville, J.: Umap: uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.03426 (2018)

[27]

Mutzel, P., Chimani, M., Gutwenger, C., Klein, K.: OGDF an open graph drawing framework. In: 15th International Symposium on Graph Drawing (2007).

[28]

Pich, C.: Applications of multidimensional scaling to graph drawing. Ph.D. thesis (2009)

[29]

Purchase H DiBattista G Which aesthetic has the greatest effect on human understanding? Graph Drawing 1997 Heidelberg Springer 248-261

[30]

Radermacher, M., Reichard, K., Rutter, I., Wagner, D.: A geometric heuristic for rectilinear crossing minimization. In: Pagh, R., Venkatasubramanian, S. (eds.) The 20th Workshop on Algorithm Engineering and Experiments (ALENEX 2018), pp. 129–138 (2018).

[31]

Ruder, S.: An overview of gradient descent optimization algorithms. CoRR abs/1609.04747 (2016). http://arxiv.org/abs/1609.04747

[32]

Seemann J DiBattista G Extending the sugiyama algorithm for drawing uml class diagrams: towards automatic layout of object-oriented software diagrams Graph Drawing 1997 Heidelberg Springer 415-424

[33]

Shabbeer, A., Ozcaglar, C., Gonzalez, M., Bennett, K.P.: Optimal embedding of heterogeneous graph data with edge crossing constraints. In: NIPS Workshop on Challenges of Data Visualization (2010)

[34]

Shepard RN The analysis of proximities: multidimensional scaling with an unknown distance function Psychometrika 1962 27 2 125-140

[35]

Sugiyama K, Tagawa S, and Toda M Methods for visual understanding of hierarchical system structures IEEE Trans. Syst. Man Cybern. 1981 11 2 109-125

[36]

Wang Y, Wang Y, Sun Y, Zhu L, Lu K, Fu C, Sedlmair M, Deussen O, and Chen B Revisiting stress majorization as a unified framework for interactive constrained graph visualization IEEE Trans. Vis. Comput. Gr. 2018 24 1 489-499

[37]

Ware C, Purchase H, Colpoys L, and McGill M Cognitive measurements of graph aesthetics Inf. Vis. 2002 1 2 103-110

Cited By

Hussain RTiezzi MCiravegna GGori M(2022)Minimizing Cross Intersections in Graph Drawing via Linear SplinesArtificial Neural Networks in Pattern Recognition10.1007/978-3-031-20650-4_3(28-39)Online publication date: 24-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20650-4_3
Ahmed RDe Luca FDevkota SKobourov SLi M(2020)Graph Drawing via Gradient Descent, Graph Drawing and Network Visualization10.1007/978-3-030-68766-3_1(3-17)Online publication date: 16-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-68766-3_1

Index Terms

Stress-Plus-X (SPX) Graph Layout

Index terms have been assigned to the content through auto-classification.

Recommendations

Queue Layout of Bipartite Graph Subdivisions

For an integer d > 0, a d-queue layout of a graph consists of a total order of the vertices, and a partition of the edges into d sets of non-nested edges with respect to the vertex ordering. Recently V. Dujmović and D. R. Wood showed that for every ...
(d+1,2) -Track Layout of Bipartite Graph Subdivisions

A ( k ,2- track layout of a graph G consists of a 2- track assignment of G and an edge k -coloring of G with no monochromatic X-crossing . This paper studies the problem of ( k ,2)-track layout of bipartite graph subdivisions. Recently V.Dujmović and ...
(3,2)-Track Layout of Bipartite Graph Subdivisions
Computational Geometry and Graph Theory

A (3,2)<em>-track layout</em> of a graph <em>G</em> consists of a 2<em>-track assignment</em> of <em>G</em> and an edge 3-coloring of <em>G</em> with no monochromatic <em>X-crossing</em> . This paper studies the problem of (3,2)-track layout of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Graph Drawing and Network Visualization: 27th International Symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019, Proceedings

Sep 2019

583 pages

ISBN:978-3-030-35801-3

DOI:10.1007/978-3-030-35802-0

Editors:
Daniel Archambault
Swansea University, Swansea, UK
,
Csaba D. Tóth
California State University, Northridge, Los Angeles, CA, USA

© Springer Nature Switzerland AG 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 September 2019

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hussain RTiezzi MCiravegna GGori M(2022)Minimizing Cross Intersections in Graph Drawing via Linear SplinesArtificial Neural Networks in Pattern Recognition10.1007/978-3-031-20650-4_3(28-39)Online publication date: 24-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20650-4_3
Ahmed RDe Luca FDevkota SKobourov SLi M(2020)Graph Drawing via Gradient Descent, Graph Drawing and Network Visualization10.1007/978-3-030-68766-3_1(3-17)Online publication date: 16-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-68766-3_1

View Options

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 Publication

Media

Figures

Other

Tables

View Table of Contents