Drawing Trees in a Streaming Model

Binucci, Carla and Brandes, Ulrik and Di Battista, Giuseppe and Didimo, Walter and Palladino, Pietro and Patrignani, Maurizio and Symvonis, Antonios and Zweig, Katharina (2010) Drawing Trees in a Streaming Model. In: Graph Drawing 17th International Symposium, GD 2009, September 22-25, 2009, Chicago, IL, USA , pp. 292-303 (Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_28).

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-11805-0_28
Classifications:P Styles > P.720 Straight-line
P Styles > P.540 Planar
M Methods > M.300 Dynamic / Incremental / Online
ID Code:1070

Repository Staff Only: item control page


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 semistreaming 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)