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

Poon, Sheung-Hung (ed.) et al., WALCOM: algorithms and computation. 11th international conference and workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10167, 135-148 (2017).
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 numbers and other aesthetic quality metrics for a graph layout, such as stress, edge-length uniformity, and edge crossings. We also investigate the performances of several graph drawing algorithms in terms of ply number, and provides new insights on the theoretical gap between lower and upper bounds on the ply number of \(k\)-ary trees.
For the entire collection see [Zbl 1358.68017].


68R10 Graph theory (including graph drawing) in computer science


OGDF; Gephi; NetworkX
Full Text: DOI


[1] Angelini, P., Bekos, M.A., Bruckdorfer, T., Hančl, J., Kaufmann, M., Kobourov, S., Symvonis, A., Valtr, P.: Low ply drawings of trees. In: Hu, Y., Nöllenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 236–248. Springer, Heidelberg (2016). doi: 10.1007/978-3-319-50106-2_19 · Zbl 1478.68210
[2] Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999) · Zbl 1226.05223
[3] Bastian, M., Heymann, S., Jacomy, M.: Gephi: an open source software for exploring and manipulating networks (2009). http://www.aaai.org/ocs/index.php/ICWSM/09/paper/view/154
[4] Buchheim, C., Jünger, M., Leipert, S.: Drawing rooted trees in linear time. Softw.: Pract. Exp. 36(6), 651–665 (2006)
[5] Chen, L., Buja, A.: Stress functions for nonlinear dimension reduction, proximity analysis, and graph drawing. J. Mach. Learn. Res. 14(1), 1145–1173 (2013) · Zbl 1319.68172
[6] Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 543–569. CRC Press, Boca Raton (2013)
[7] Chrobak, M., Kant, G.: Convex grid drawings of 3-connected planar graphs. Int. J. Comput. Geom. Appl. 07(03), 211–223 (1997) · Zbl 05472183
[8] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999) · Zbl 1057.68653
[9] Di Giacomo, E., Didimo, W., Hong, S.H., Kaufmann, M., Kobourov, S.G., Liotta, G., Misue, K., Symvonis, A., Yen, H.C.: Low ply graph drawing. In: IISA 2015, pp. 1–6. IEEE (2015)
[10] Didimo, W., Liotta, G.: Mining graph data. In: Cook, D.J., Holder, L.B. (eds.) Graph Visualization and Data Mining, pp. 35–64. Wiley, Hoboken (2007)
[11] Dwyer, T., Lee, B., Fisher, D., Quinn, K.I., Isenberg, P., Robertson, G.G., North, C.: A comparison of user-generated and automatic graph layouts. IEEE Trans. Vis. Comput. Graph. 15(6), 961–968 (2009)
[12] Eades, P.: A heuristics for graph drawing. Congressus Numerantium 42, 146–160 (1984)
[13] Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: GIS 2008, pp. 1–10. ACM (2008)
[14] de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990) · Zbl 0728.05016
[15] Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration). In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995). doi: 10.1007/3-540-58950-3_393
[16] Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw.: Pract. Exp. 21(11), 1129–1164 (1991)
[17] Gansner, E.R., Koren, Y., North, S.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-31843-9_25 · Zbl 1111.68580
[18] Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-31843-9_29 · Zbl 1111.68583
[19] Hachul, S., Jünger, M.: Large-graph layout algorithms at work: an experimental study. J. Graph Algorithms Appl. 11(2), 345–369 (2007) · Zbl 1161.68672
[20] Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using networkX. In: Varoquaux, G., Vaught, T., Millman, J. (eds.) Proceedings of the 7th Python in Science Conference, Pasadena, CA, USA, pp. 11–15 (2008)
[21] Huang, W., Hong, S.H., Eades, P.: Effects of sociogram drawing conventions and edge crossings in social network visualization. J. Graph Algorithms Appl. 11(2), 397–429 (2007) · Zbl 05493588
[22] Jünger, M., Mutzel, P. (eds.): Graph Drawing Software. Springer, Heidelberg (2003) · Zbl 1029.68145
[23] Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31(1), 7–15 (1989) · Zbl 0679.68128
[24] Kobourov, S.G.: Force-directed drawing algorithms. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 383–408. CRC Press, Boca Raton (2013)
[25] Kobourov, S.G., Pupyrev, S., Saket, B.: Are crossings important for drawing large graphs? In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 234–245. Springer, Heidelberg (2014). doi: 10.1007/978-3-662-45803-7_20 · Zbl 1426.68219
[26] Kruskal, J.B., Wish, M.: Multidimensional Scaling. Sage Press, Thousand Oaks (1978)
[27] Noack, A.: Energy models for graph clustering. J. Graph Algorithms Appl. 11(2), 453–480 (2007) · Zbl 1161.68691
[28] Prüfer, H.: Neuer beweis eines satzesüber permutationen. Arch. Math. Phys. 27, 742–744 (1918) · JFM 46.0106.04
[29] Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interact. Comput. 13(2), 147–162 (2000) · Zbl 05425663
[30] Purchase, H.C., Carrington, D.A., Allder, J.A.: Empirical evaluation of aesthetics-based graph layout. Empir. Softw. Eng. 7(3), 233–255 (2002) · Zbl 1010.68636
[31] Reingold, E.M., Tilford, J.S.: Tidier drawings of trees. IEEE Trans. Softw. Eng. SE-7(2), 223–228 (1981) · Zbl 05341324
[32] Spearman, C.: The proof and measurement of association between two things. Am. J. Psychol. 15(1), 72–99 (1904)
[33] Tamassia, R. (ed.): Handbook of Graph Drawing and Visualization. CRC Press, Boca Raton (2013) · Zbl 1275.68033
[34] Walker, J.Q.: A node-positioning algorithm for general trees. Softw.: Pract. Exp. 20(7), 685–705 (1990)
[35] Ware, C., Purchase, H.C., Colpoys, L., McGill, M.: Cognitive measurements of graph aesthetics. Inf. Vis. 1(2), 103–110 (2002) · Zbl 02181749
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.