Graph Animation

In several applications there is the need of visualizing a graph whose structure evolves over time. A few examples: in the networking field it is often necessary to show how the flow of packets changes according to network modifications; in the Internet Domain Name System it is useful to study the evolution of the relationship between name servers sending queries and name servers answering such queries; and in Web crawling it is interesting to study, during the Web exploration, how the structure of the visited hyperlinks depends on the actual search strategy. From the point of view of the graph visualization field these animation requirements pose difficult challenges for at least three reasons. First, instead of constructing just one layout of one graph, graph animation requires to construct several layouts, depending on the duration of the animation. This poses nontrivial efficiency issues. Second, the user's mental map should be preserved. Hence, the graph layouts of consecutive steps cannot be too much different. Third, to help the user in easily perceiving the changes, morphing problems must be tackled. Namely, the same portion of the graph might be represented in two different ways in two different times of the animation. Hence, the problem arises of how to compute a smooth morphing between the two representations. I will survey experiences of graph animation at the Network Visualization Lab of the Università Roma Tre both from the pragmatic and from the methodological points of view.