TY - GEN
T1 - Visualizing Evolving Trees
AU - Gray, Kathryn
AU - Li, Mingwei
AU - Ahmed, Reyan
AU - Kobourov, Stephen
N1 - Funding Information:
Abstract. Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github. (This work was supported in part by NSF grants CCF-1740858, CCF-1712119, and DMS-1839274.)
Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github. (This work was supported in part by NSF grants CCF-1740858, CCF-1712119, and DMS-1839274.)
AB - Evolving trees arise in many real-life scenarios from computer file systems and dynamic call graphs, to fake news propagation and disease spread. Most layout algorithms for static trees do not work well in an evolving setting (e.g., they are not designed to be stable between time steps). Dynamic graph layout algorithms are better suited to this task, although they often introduce unnecessary edge crossings. With this in mind we propose two methods for visualizing evolving trees that guarantee no edge crossings, while optimizing (1) desired edge length realization, (2) layout compactness, and (3) stability. We evaluate the two new methods, along with five prior approaches (three static and two dynamic), on real-world datasets using quantitative metrics: stress, desired edge length realization, layout compactness, stability, and running time. The new methods are fully functional and available on github. (This work was supported in part by NSF grants CCF-1740858, CCF-1712119, and DMS-1839274.)
UR - http://www.scopus.com/inward/record.url?scp=85148697321&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85148697321&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-22203-0_23
DO - 10.1007/978-3-031-22203-0_23
M3 - Conference contribution
AN - SCOPUS:85148697321
SN - 9783031222023
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 319
EP - 335
BT - Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
A2 - Angelini, Patrizio
A2 - von Hanxleden, Reinhard
PB - Springer Science and Business Media Deutschland GmbH
T2 - 30th International Symposium on Graph Drawing and Network Visualization, GD 2022
Y2 - 13 September 2022 through 16 September 2022
ER -