×

An interactive tool to explore and improve the ply number of drawings. (English) Zbl 1503.68221

Frati, Fabrizio (ed.) et al., Graph drawing and network visualization. 25th international symposium, GD 2017, Boston, MA, USA, September 25–27, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10692, 38-51 (2018).
Summary: Given a straight-line drawing \(\varGamma\) of a graph \(G=(V,E)\), for every vertex \(v\) the ply disk \(D_v\) is defined as a disk centered at \(v\) where the radius of the disk is half the length of the longest edge incident to \(v\). The ply number of a given drawing is defined as the maximum number of overlapping disks at some point in \(\mathbb R^2\). Here we present a tool to explore and evaluate the ply number for graphs with instant visual feedback for the user. We evaluate our methods in comparison to an existing ply computation by F. De Luca et al. [Lect. Notes Comput. Sci. 10167, 135–148 (2017; Zbl 1485.68178)]. We are able to reduce the computation time from seconds to milliseconds for given drawings and thereby contribute to further research on the ply topic by providing an efficient tool to examine graphs extensively by user interaction as well as some automatic features to reduce the ply number.
For the entire collection see [Zbl 1381.68007].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 1485.68178

Software:

Ply; apfloat; yFiles; OGDF
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Angelini, P.; Bekos, MA; Bruckdorfer, T.; Hančl, J.; Kaufmann, M.; Kobourov, S.; Symvonis, A.; Valtr, P.; Hu, Y.; Nöllenburg, M., Low ply drawings of trees, Graph Drawing and Network Visualization, 236-248 (2016), Cham: Springer, Cham · Zbl 1469.11479 · doi:10.1007/978-3-319-50106-2_19
[2] Angelini, P., Chaplick, S., De Luca, F., Fiala, J., Hancl, J., Heinsohn, N., Kaufmann, M., Kobourov, S., Kratochvil, J., Valtr, P.: On vertex- and empty-ply proximity drawings. In: Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) (2017, to appear) · Zbl 1407.81084
[3] Atallah, MJ, Algorithms and Theory of Computation Handbook (1999), Boca Raton: CRC Press, Boca Raton · Zbl 1380.94081
[4] Bachus, L.: Ply, University of Tübingen. Bachelor thesis (2016)
[5] Brandes, U., Eiglsperger, M., Lerner, J., Pich, C.: Graph markup language (GraphML). In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 517-541. Chapman and Hall/CRC (2013)
[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 on Graph Drawing and Visualization, pp. 543-569. Chapman and Hall/CRC (2013) · Zbl 1420.94060
[7] De Luca, F.; Di Giacomo, E.; Didimo, W.; Kobourov, S.; Liotta, G.; Poon, S-H; Rahman, MS; Yen, H-C, An experimental study on the ply number of straight-line drawings, WALCOM: Algorithms and Computation, 135-148 (2017), Cham: Springer, Cham · Zbl 1284.14035 · doi:10.1007/978-3-319-53925-6_11
[8] Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall (1999) · Zbl 1466.94028
[9] Di Giacomo, E., Didimo, W., Hong, S., Kaufmann, M., Kobourov, S.G., Liotta, G., Misue, K., Symvonis, A., Yen, H.: Low ply graph drawing. In: Bourbakis, N.G., Tsihrintzis, G.A., Virvou, M. (eds.) 6th International Conference on Information, Intelligence, Systems and Applications, IISA 2015, Corfu, Greece, 6-8 July 2015, pp. 1-6. IEEE (2015) · Zbl 1290.94094
[10] Eppstein, D., Goodrich, M.T.: Studying (non-planar) road networks through an algorithmic lens. In: Aref, W.G., Mokbel, M.F., Schneider, M. (eds.) 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, ACM-GIS 2008, Proceedings, 5-7 November 2008, Irvine, California, USA, p. 16. ACM (2008)
[11] Fruchterman, TMJ; Reingold, EM, Graph drawing by force-directed placement, Softw., Pract. Exper., 21, 11, 1129-1164 (1991) · Zbl 1458.94251 · doi:10.1002/spe.4380211102
[12] Hachul, S.; Jünger, M.; Pach, J., Drawing large graphs with a potential-field-based multilevel algorithm, Graph Drawing, 285-295 (2005), Heidelberg: Springer, Heidelberg · Zbl 1111.68583 · doi:10.1007/978-3-540-31843-9_29
[13] Hachul, S.; Jünger, M., Large-graph layout algorithms at work: an experimental study, J. Graph Algorithms Appl., 11, 2, 345-369 (2007) · Zbl 1339.14026 · doi:10.7155/jgaa.00150
[14] Himsolt, M.: GML: A Portable Graph File Format. Universität Passau (1997). http://www.fmi.uni-passau.de/graphlet/gml/gml-tr.html · Zbl 1459.94105
[15] Kobourov, S.G.: Force-directed drawing algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 383-408. Chapman and Hall/CRC (2013) · Zbl 1194.11005
[16] Tamassia, R., Liotta, G.: Graph drawing. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 1163-1185. Chapman and Hall/CRC (2004) · Zbl 1056.52001
[17] Tommila, M.: A C++ high performance arbitrary precision arithmetic package (2003). http://www.apfloat.org/apfloat/ · Zbl 1404.14053
[18] Welzl, E.; Di Battista, G.; Garg, A.; Liotta, G.; Tamassia, R.; Tassinari, E.; Vargiu, F., An experimental comparison of four graph drawing algorithms, Comput. Geom., 7, 303-325 (1997) · Zbl 1133.68460 · doi:10.1016/S0925-7721(97)00002-3
[19] Wiese, R.; Eiglsperger, M.; Kaufmann, M.; Jünger, M.; Mutzel, P., yFiles - visualization and automatic layout of graphs, Graph Drawing Software, 173-191 (2004), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-18638-7_8
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.