Offline drawing of dynamic trees: algorithmics and document integration

DOI10.1007/978-3-319-50106-2_44MaRDI QIDQ2961550zbMATH OpenOpenAlexFDO

Authors Malte Skambath, Till Tantau

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.08385

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Drawing trees and animating tree changes
• Depth-first layout algorithm for trees.
• Drawing trees in a streaming model
• Drawing trees in a streaming model
• Algorithms for drawing binary trees in the plane.

Cites work

• scientific article; zbMATH DE number 2084318 (Why is no real title available?)
• scientific article; zbMATH DE number 30296 (Why is no real title available?)
• scientific article; zbMATH DE number 1754564 (Why is no real title available?)
• Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar ST-Digraphs
• Graph Drawing
• Graph drawing in TikZ
• Offline drawing of dynamic trees: algorithmics and document integration
• Optimum binary search trees
• Tidy Drawings of Trees

Cited in

(13)

• Drawing trees in a streaming model
• scientific article; zbMATH DE number 1974133 (Why is no real title available?)
• Visualizing evolving trees
• Graph Stories in Small Area
• Small Point-Sets Supporting Graph Stories
• Small point-sets supporting graph stories
• On the complexity of the storyplan problem
• On the complexity of the storyplan problem
• Visualization of barrier tree sequences revisited
• Graph drawing in Ti\(k\)Z
• Offline drawing of dynamic trees: algorithmics and document integration
• Drawing trees and animating tree changes
• Graph stories in small area

Describes a project that uses

Uses Software

• Nevada
• Dynagraph
• Lua
• TikZ
• OGDF
• SMIL
• Graphviz

This page was built for publication: Offline drawing of dynamic trees: algorithmics and document integration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961550)