×

Offline drawing of dynamic trees: algorithmics and document integration. (English) Zbl 1478.68260

Hu, Yifan (ed.) et al., Graph drawing and network visualization. 24th international symposium, GD 2016, Athens, Greece, September 19–21, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9801, 572-586 (2016).
Summary: While the algorithmic drawing of static trees is well-understood and well-supported by software tools, creating animations depicting how a tree changes over time is currently difficult: software support, if available at all, is not integrated into a document production workflow and algorithmic approaches only rarely take temporal information into consideration. During the production of a presentation or a paper, most users will visualize how, say, a search tree evolves over time by manually drawing a sequence of trees. We present an extension of the popular TEX typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running TEX on the documents then results in documents in the svg format with visually pleasing embedded animations. Our algorithm produces animations that satisfy a set of natural aesthetic criteria when possible. On the negative side, we show that one cannot always satisfy all criteria simultaneously and that minimizing their violations is NP-complete.
For the entire collection see [Zbl 1352.68012].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68U15 Computing methodologies for text processing; mathematical typography
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adelson-Velsky, G.M., Landis, E.M.: An algorithm for the organization of information. Dokl. Akad. Nauk USSR 3(2), 1259–1263 (1962)
[2] Archambault, D., Purchase, H., Pinaud, B.: Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE Trans. Visual. Comput. Graph. 17(4), 539–552 (2011) · doi:10.1109/TVCG.2010.78
[3] Archambault, D., Purchase, H.C.: The mental map and memorability in dynamic graphs. In: Proceedings of Visualization Symposium (PacificVis) 2012, pp. 89–96. IEEE Press (2012) · doi:10.1109/PacificVis.2012.6183578
[4] Bartram, L., Ware, C.: Filtering and brushing with motion. Inf. Visual. 1(1), 66–79 (2002) · doi:10.1057/palgrave.ivs.9500005
[5] Beck, F., Burch, M., Diehl, S., Weiskopf, D.: The state of the art in visualizing dynamic graphs. In: State of the Art Reports of the 16th Eurographics Conference on Visualization, EuroVis 2014, pp. 83–103. Eurographics Association (2014)
[6] Brüggemann-Klein, A., Wood, D.: Drawing trees nicely with TeX. Electron. Publishing 2(2), 101–115 (1989)
[7] Bulterman, D., Jansen, J., Cesar, P., Mullender, S., Hyche, E., DeMeglio, M., Quint, J., Kawamura, H., Weck, D., García Pañeda, X., Melendi, D., Cruz-Lara, S., Hanclik, M., Zucker, D.F., Michel, T.: Synchronized multimedia integration language (SMIL 3.0), W3C Recommendation 01 December 2008. Technical report REC-SMIL3-20081201, The World Wide Web Consortium (W3C) (2008). http://www.w3.org/TR/2008/REC-SMIL3-20081201
[8] Burch, M., Beck, F., Weiskopf, D.: Radial edge splatting for visualizing dynamic directed graphs. In: Proceedings of the International Conference on Computer Graphics Theory and Applications, IVAPP 2012, pp. 603–612. SciTe Press (2012)
[9] Burch, M., Diehl, S.: TimeRadarTrees: visualizing dynamic compound digraphs. Comput. Graph. Forum 27(3), 823–830 (2008) · Zbl 05653307 · doi:10.1111/j.1467-8659.2008.01213.x
[10] Chimani, M., Gutwenger, C., Jünger, M., Klein, K., Mutzel, P., Schulz, M.: The open graph drawing framework. In: Poster at the 15th International Symposium on Graph Drawing 2007 (GD 2007) (2007)
[11] Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G.: Dynamic graph drawings: trees, series-parallel digraphs, and planar st-digraphs. SIAM J. Comput. 24(5), 970–1001 (1995) · Zbl 0836.68041 · doi:10.1137/S0097539792235724
[12] Cohen, R.F., Di Battista, G., Tamassia, R., Tollis, I.G., Bertolazzi, P.: A framework for dynamic graph drawing. In: Proceedings of the 8th Annual Symposium on Computational Geometry, SCG 1992, pp. 261–270. ACM Press (1992) · doi:10.1145/142675.142728
[13] Dahlström, E., Dengler, P., Grasso, A., Lilley, C., McCormack, C., Schepers, D., Watt, J.: Scalable vector graphics (SVG) 1.1 (2nd edn. ), W3C Recommendation 16 August 2011. Technical report REC-SVG11-20110816, The World Wide Web Consortium (W3C) (2011). http://www.w3.org/TR/2011/REC-SVG11-20110816
[14] Diehl, S., Görg, C., Kerren, A.: Foresighted graphlayout. Technical report A/02/2000, FB Informatik, University Saarbrücken, Saarbrücken, Germany (2000)
[15] Diehl, S., Görg, C., Kerren, A.: Preserving the mental map using foresighted layout. In: Proceedings of the 3rd Joint Eurographics-IEEE TCVG Conference on Visualization, vol. 1, pp. 175–184. The Eurographics Association (2001) · Zbl 1016.68130 · doi:10.1007/978-3-7091-6215-6_19
[16] Eades, P., Sugiyama, K.: How to draw a directed graph. J. Inf. Process. 13(4), 424–436 (1990) · Zbl 0764.68114
[17] Ellson, J., Gansner, E.R., Koutsofios, E., North, S.C., Woodhull, G.: Graphviz and dynagraph - static and dynamic graph drawing tools. In: Junger, M., Mutzel, P. (eds.) Graph Drawing Software. Mathematics and Visualization, pp. 127–148. Springer, Heidelberg (2004) · Zbl 1054.68583 · doi:10.1007/978-3-642-18638-7_6
[18] Eppstein, D.: Trees in TeX. TUGboat 6(1), 31–35 (1985)
[19] Federico, P., Aigner, W., Miksch, S., Windhager, F., Zenk, L.: A visual analytics approach to dynamic social networks. In: Proceedings of the 11th International Conference on Knowledge Management and Knowledge Technologies, i-KNOW 2011, pp. 47:1–47:8. ACM Press (2011) · doi:10.1145/2024288.2024344
[20] Görg, C., Birke, P., Pohl, M., Diehl, S.: Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 228–238. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-31843-9_24 · Zbl 1111.68581 · doi:10.1007/978-3-540-31843-9_24
[21] Graham, M., Kennedy, J.: A survey of multiple tree visualisation. Inf. Visual. 9(4), 235–252 (2010) · doi:10.1057/ivs.2009.29
[22] Greilich, M., Burch, M., Diehl, S.: Visualizing the evolution of compound digraphs with TimeArcTrees. Comput. Graph. Forum 28(3), 975–982 (2009) · Zbl 05650563 · doi:10.1111/j.1467-8659.2009.01451.x
[23] Groh, G., Hanstein, H., Wörndl, W.: Interactively visualizing dynamic social networks with DySoN. In: Proceedings of the Workshop on Visual Interfaces to the Social and the Semantic Web, VISSW 2009 (2009)
[24] Ierusalimschy, R.: Programming in Lua, 2nd edn. Lua.org, San Francisco (2006)
[25] Johnson, B., Shneiderman, B.: Tree-maps: a space-filling approach to the visualization of hierarchical information structures. In: Proceedings of the 2nd IEEE Conference on Visualization 1991, VIS 1991, pp. 284–291. IEEE Press (1991) · doi:10.1109/VISUAL.1991.175815
[26] Knuth, D.E.: Optimum binary search trees. Acta Informatica 1(1), 14–25 (1971) · Zbl 0233.68010 · doi:10.1007/BF00264289
[27] Moen, S.: Drawing dynamic trees. IEEE Softw. 7(4), 21–28 (1990) · Zbl 05101957 · doi:10.1109/52.56447
[28] Reda, K., Tantipathananandh, C., Johnson, A., Leigh, J., Berger-Wolf, T.: Visualizing the evolution of community structures in dynamic social networks. Comput. Graph. Forum 30(3), 1061–1070 (2011) · doi:10.1111/j.1467-8659.2011.01955.x
[29] Reingold, E.M., Tilford, J.S.: Tidier drawings of trees. IEEE Trans. Softw. Eng. 7(2), 223–228 (1981) · Zbl 05341324 · doi:10.1109/TSE.1981.234519
[30] Robertson, G.G., Mackinlay, J.D., Card, S.K.: Cone trees: Animated 3D visualizations of hierarchical information. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI 1991, pp. 189–194. ACM Press (1991) · doi:10.1145/108844.108883
[31] Skambath, M.: Algorithmic drawing of evolving trees. Master’s thesis, Institute of Theoretical Computer Science, Universität zu Lübeck, Germany (2016)
[32] Skambath, M., Tantau, T.: Offline drawing of dynamic trees: algorithmics and document integration. SVG Version of this document. http://www.informatik.uni-kiel.de/ msk/pub/2016-dynamic-trees/main.html · Zbl 1478.68260
[33] Stasko, J., Zhang, E.: Focus+context display and navigation techniques for enhancing radial, space-filling hierarchy visualizations. In: Proceedings of the IEEE Symposium on Information Vizualization 2000, INFOVIS 2000, pp. 57–65. IEEE Press (2000) · doi:10.1109/INFVIS.2000.885091
[34] Sugiyama, K., Tagawa, S., Toda, M.: Effective representations of hierarchical structures. Technical report 8, International Institute for Advanced Study of Social Information Science, Fujitsu (1979)
[35] Sweet, R.E.: Empirical estimates of program entropy. Report Stan-CS-78-698, Department of Computer Science, Stanford University, Stanford, CA, USA (1978)
[36] Tantau, T.: Graph drawing in TikZ. J. Graph Algorithms Appl. 17(4), 495–513 (2013) · Zbl 1396.68081 · doi:10.7155/jgaa.00301
[37] Tantau, T.: The TikZ and pgf packages, manual for version 3.0.0 (2015). http://sourceforge.net/projects/pgf/
[38] Walker II, J.Q.: A node-positioning algorithm for general trees. Softw.: Pract. Exp. 20(7), 685–705 (1990)
[39] Ware, C., Bobrow, R.: Motion to support rapid interactive queries on node-link diagrams. ACM Trans. Appl. Percept. 1(1), 3–18 (2004) · doi:10.1145/1008722.1008724
[40] Wetherell, C., Shannon, A.: Tidy drawings of trees. IEEE Trans. Softw. Eng. 5(5), 514–520 (1979) · Zbl 0412.68092 · doi:10.1109/TSE.1979.234212
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.