Abstract
We introduce a data stream model of computation for Graph Drawing, where a source produces a graph one edge at a time. When an edge is produced, it is immediately drawn and its drawing can not be altered. The drawing has an image persistence, that controls the lifetime of edges. If the persistence is k, an edge remains in the drawing for the time spent by the source to generate k edges, then it fades away. In this model we study the area requirement of planar straight-line grid drawings of trees, with different streaming orders, layout models, and quality criteria. We assess the output quality of the presented algorithms by computing the competitive ratio with respect to the best known offline algorithms.
Work on this problem began at the BICI Workshop on Graph Drawing: Visualization of Large Graphs, held in Bertinoro, Italy, in March 2008.
Chapter PDF
Similar content being viewed by others
References
Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proc. SODA, pp. 623–632 (2002)
Bárány, I., Tokushige, N.: The minimum area of convex lattice n-gons. Combinatorica 24(2), 171–185 (2004)
Biedl, T., Kant, G.: A better heuristic for orthogonal graph drawings. Computational Geometry 9, 159–180 (1998)
Branke, J.: Dynamic graph drawing. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 228–246. Springer, Heidelberg (2001)
Buriol, L., Donato, D., Leonardi, S., Matzner, T.: Using data stream algorithms for computing properties of large graphs. In: Proc. Workshop on Massive Geometric Datasets (MASSIVE 2005), pp. 9–14 (2005)
Crescenzi, P., Di Battista, G., Piperno, A.: A note on optimal area algorithms for upward drawings of binary trees. Comput. Geom. Theory Appl. 2, 187–200 (1992)
de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10, 41–51 (1990)
Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 531–543. Springer, Heidelberg (2004)
Garg, A., Rusu, A.: Straight-line drawings of binary trees with linear area and arbitrary aspect ratio. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 320–331. Springer, Heidelberg (2002)
Garg, A., Rusu, A.: Straight-line drawings of general trees with linear area and arbitrary aspect ratio. In: Kumar, V., Gavrilova, M.L., Tan, C.J.K., L’Ecuyer, P. (eds.) ICCSA 2003. LNCS, vol. 2669, pp. 876–885. Springer, Heidelberg (2003)
Huang, M.L., Eades, P., Wang, J.: On-line animated visualization of huge graphs using a modified spring algorithm. J. Vis. Lang. Comput. 9(6), 623–645 (1998)
Muthukrishnan, S.: Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science 1(2), 117–236 (2005)
Papakostas, A., Tollis, I.G.: Interactive orthogonal graph drawing. IEEE Trans. Computers 47(11), 1297–1309 (1998)
Shiloach, Y.: Arrangements of Planar Graphs on the Planar Lattice. Ph.D. thesis, Weizmann Institute of Science (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Binucci, C. et al. (2010). Drawing Trees in a Streaming Model. In: Eppstein, D., Gansner, E.R. (eds) Graph Drawing. GD 2009. Lecture Notes in Computer Science, vol 5849. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11805-0_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-11805-0_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-11804-3
Online ISBN: 978-3-642-11805-0
eBook Packages: Computer ScienceComputer Science (R0)