Offline Drawing of Dynamic Trees: Algorithmics and Document Integration

Skambath, Malte and Tantau, Till (2016) Offline Drawing of Dynamic Trees: Algorithmics and Document Integration. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 572-586(Official URL:

Full text not available from this repository.


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 typesetting system that allows users to specify dynamic trees inside their documents, together with a new algorithm for drawing them. Running 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.

Item Type: Conference Paper
Classifications: M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.900 Tree
P Styles > P.720 Straight-line

Actions (login required)

View Item View Item