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 , pp. 292-303(Official URL: http://dx.doi.org/10.1007/978-3-642-11805-0_28).

Full text not available from this repository.

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.

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1070

Actions (login required)

View Item View Item