An experimental study on the ply number of straight-line drawings. (English) Zbl 1405.05124

Summary: The ply number of a drawing is a new criterion of interest for graph drawing. Informally, the ply number of a straight-line drawing of a graph is defined as the maximum number of overlapping disks, where each disk is associated with a vertex and has a radius that is half the length of the longest edge incident to that vertex. This paper reports the results of an extensive experimental study that attempts to estimate correlations between the ply number and other aesthetic quality metrics for a graph layout, such as stress, edge-length uniformity, and edge crossings. We also investigate the performance of several graph drawing algorithms in terms of ply number, and provide new insights into the theoretical gap between lower and upper bounds on the ply number of \(k\)-ary trees.


05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)


NetworkX; Gephi; OGDF; Ply
Full Text: DOI


[1] P. Angelini, M. A. Bekos, T. Bruckdorfer, J. H. Jr., M. Kaufmann, S. G. Kobourov, A. Symvonis, and P. Valtr. Low ply drawings of trees. In Y. Hu and M. N¨ollenburg, editors, Graph Drawing and Network Visualization, GD 2016, volume 9801 of LNCS, pages 236–248. Springer, 2016. · Zbl 1478.68210
[2] P. Angelini, S. Chaplick, F. D. Luca, J. Fiala, J. H. Jr., N. Heinsohn, M. Kaufmann, S. G. Kobourov, J. Kratochv´ıl, and P. Valtr. On vertexand empty-ply proximity drawings. In F. Frati and K. Ma, editors, Graph Drawing and Network Visualization, GD 2017, volume 10692 of LNCS, pages 24–37. Springer, 2017.
[3] A.-L. Barab´asi and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999. · Zbl 1226.05223
[4] M. Bastian, S. Heymann, and M. Jacomy. Gephi: An open source software for exploring and manipulating networks. 2009.
[5] C. Buchheim, M. J¨unger, and S. Leipert. Drawing rooted trees in linear time. Software: Practice and Experience, 36(6):651–665, 2006.
[6] L. Chen and A. Buja. Stress functions for nonlinear dimension reduction, proximity analysis, and graph drawing. The Journal of Machine Learning Research, 14(1):1145–1173, 2013. · Zbl 1319.68172
[7] M. Chimani, C. Gutwenger, M. J¨unger, G. W. Klau, K. Klein, and P. Mutzel. The open graph drawing framework (OGDF). In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, pages 543–569. CRC Press, 2013.
[8] M. Chrobak and G. Kant. Convex grid drawings of 3-connected planar graphs. International Journal of Computational Geometry & Applications, 07(03):211–223, 1997.
[9] H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990. · Zbl 0728.05016
[10] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, 1999. · Zbl 1057.68653
[11] E. Di Giacomo, W. Didimo, S.-H. Hong, M. Kaufmann, S. G. Kobourov, G. Liotta, K. Misue, A. Symvonis, and H.-C. Yen. Low ply graph drawing. In 2015 6th International Conference on Information, Intelligence, Systems and Applications, pages 1–6. IEEE, 2015.
[12] W. Didimo and G. Liotta. Mining graph data. In D. J. Cook and L. B. Holder, editors, Graph Visualization and Data Mining, pages 35–64. Wiley, 2007.
[13] T. Dwyer, B. Lee, D. Fisher, K. I. Quinn, P. Isenberg, G. G. Robertson, and C. North. A comparison of user-generated and automatic graph layouts. IEEE Transanction on Visualization and Computer Graphics, 15(6):961– 968, 2009.
[14] P. Eades. A heuristics for graph drawing. Congressus numerantium, 42:146– 160, 1984.
[15] D. Eppstein and M. T. Goodrich. Studying (non-planar) road networks through an algorithmic lens. In GIS 2008, pages 1–10. ACM, 2008.
[16] A. Frick, A. Ludwig, and H. Mehldau. A fast adaptive layout algorithm for undirected graphs.In R. Tamassia and I. G. Tollis, editors, GD ’ 94, volume 894 of LNCS, pages 388–403. Springer, 1995.
[17] T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Software: Practice and Experience, 21(11):1129–1164, 1991.
[18] E. R. Gansner, Y. Koren, and S. C. North. Graph drawing by stress majorization.In J. Pach, editor, GD 2004, volume 3383 of LNCS, pages 239–250. Springer, 2004. · Zbl 1111.68580
[19] S. Hachul and M. J¨unger. Drawing large graphs with a potential-field-based multilevel algorithm. In J. Pach, editor, GD 2004, volume 3383 of LNCS, pages 285–295. Springer, 2004. · Zbl 1111.68583
[20] S. Hachul and M. J¨unger.Large-graph layout algorithms at work: An experimental study. Journal of Graph Algorithms and Applications, 11(2):345–369, 2007. · Zbl 1161.68672
[21] A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring network structure, dynamics, and function using NetworkX. In G. Varoquaux, T. Vaught, and J. Millman, editors, Proceedings of the 7th Python in Science Conference, pages 11–15, 2008.
[22] N. Heinsohn and M. Kaufmann. An interactive tool to explore and improve the ply number of drawings. In F. Frati and K. Ma, editors, Graph Drawing and Network Visualization, GD 2017, volume 10692 of LNCS, pages 38–51. Springer, 2017.
[23] W. Huang, S.-H. Hong, and P. Eades.Effects of sociogram drawing conventions and edge crossings in social network visualization.Journal of Graph Algorithms and Applications, 11(2):397–429, 2007.
[24] M. J¨unger and P. Mutzel, editors. Graph Drawing Software. Springer, 2003. · Zbl 1029.68145
[25] T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7–15, 1989. · Zbl 0679.68128
[26] S. G. Kobourov. Force-directed drawing algorithms. In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, pages 383–408. CRC Press, 2013.
[27] S. G. Kobourov, S. Pupyrev, and B. Saket. Are crossings important for drawing large graphs? In C. A. Duncan and A. Symvonis, editors, Graph Drawing, Revised Selected Papers, volume 8871 of LNCS, pages 234–245. Springer, 2014. · Zbl 1426.68219
[28] J. B. Kruskal and M. Wish. Multidimensional Scaling. Sage Press, 1978.
[29] D. Mondal and L. Nachmanson. A new approach to graphmaps, a system browsing large graphs as interactive maps. CoRR, abs/1705.05479, 2017.
[30] L. Nachmanson, R. Prutkin, B. Lee, N. H. Riche, A. E. Holroyd, and X. Chen. Graphmaps: Browsing large graphs as interactive maps. CoRR, abs/1506.06745, 2015. · Zbl 1471.68207
[31] A. Noack. Energy models for graph clustering. Journal of Graph Algorithms and Applications, 11(2):453–480, 2007. · Zbl 1161.68691
[32] H. Pr¨ufer.Neuer beweis eines satzes¨uber permutationen.Arch. Math. Phys., 27:742–744, 1918.
[33] H. C. Purchase. Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interacting with Computers, 13(2):147–162, 2000.
[34] H. C. Purchase, D. Carrington, and J.-A. Allder. Empirical evaluation of aesthetics-based graph layout. Empirical Software Engineering, 7(3):233– 255, 2002. · Zbl 1010.68636
[35] E. M. Reingold and J. S. Tilford. Tidier drawings of trees. IEEE Transactions on Software Engineering, SE-7(2):223–228, 1981.
[36] C. Spearman.The proof and measurement of association between two things. American Journal of Psychology, 15(1):72–99, 1904.
[37] R. Tamassia, editor. Handbook of Graph Drawing and Visualization. CRC Press, 2013.
[38] J. Q. Walker.A node-positioning algorithm for general trees.Software: Practice and Experience, 20(7):685–705, 1990.
[39] C. Ware, H. C. Purchase, L. Colpoys, and M. McGill. Cognitive measurements of graph aesthetics. Information Visualization, 1(2):103–110, 2002.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.