Exploring the dynamics of graph algorithms
Open Access
- 14 October 2022
- journal article
- research article
- Published by Springer Nature in Journal of Visualization
- Vol. 26 (2) , 477-492
Abstract
In this paper, we describe an interactive visualization tool for representing the dynamics of graph algorithms. To reach this goal, we designed a web-based framework which illustrates the dynamics as time-to-space mappings of dynamic graphs. Such static diagrams of dynamic data have the benefit of being able to display longer time spans in one view, hence supporting the observer with comparison tasks which is challenging or even impossible for graph algorithm animations. Our tool can show details about how an algorithm traverses a graph step-by-step in a static and animated fashion, for graph algorithm exploration as well as educational purposes. The animation together with the time-to-space mapping hence forms an overview-and-detail approach. We also allow changing of speed, replaying, stopping, storing intermediate stages with parameter configurations, as well as measuring and monitoring performance and memory consumption to eventually identify bottlenecks in a graph algorithm. By using flight carrier data from the United States Department of Transportation and a network of autonomous systems we demonstrate how we used the tool to explore two standard graph-theoretic algorithms. Finally, we discuss scalability issues and limitations. Graphical abstractKeywords
This publication has 36 references indexed in Scilit:
- Visual Analysis of Large Graphs: State‐of‐the‐Art and Future Research ChallengesComputer Graphics Forum, 2011
- Visualizing the Evolution of Compound Digraphs with TimeArcTreesComputer Graphics Forum, 2009
- A review of overview+detail, zooming, and focus+context interfacesACM Computing Surveys, 2009
- How Important Is the “Mental Map”? – An Empirical Investigation of a Dynamic Graph Layout Algorithm2007
- Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs2005
- Graphsplatting: visualizing graphs as continuous fieldsIEEE Transactions on Visualization and Computer Graphics, 2003
- Animation: can it facilitate?International Journal of Human-Computer Studies, 2002
- Layout Adjustment and the Mental MapJournal of Visual Languages & Computing, 1995
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Shortest Connection Networks And Some GeneralizationsBell System Technical Journal, 1957