Improving Temporal Treemaps by Minimizing Crossings
| dc.contributor.author | Dobler, Alexander | en_US |
| dc.contributor.author | Nöllenburg, Martin | en_US |
| dc.contributor.editor | Aigner, Wolfgang | en_US |
| dc.contributor.editor | Archambault, Daniel | en_US |
| dc.contributor.editor | Bujack, Roxana | en_US |
| dc.date.accessioned | 2024-05-21T08:18:07Z | |
| dc.date.available | 2024-05-21T08:18:07Z | |
| dc.date.issued | 2024 | |
| dc.description.abstract | Temporal trees are trees that evolve over a discrete set of time steps. Each time step is associated with a node-weighted rooted tree and consecutive trees change by adding new nodes, removing nodes, splitting nodes, merging nodes, and changing node weights. Recently, two-dimensional visualizations of temporal trees called temporal treemaps have been proposed, representing the temporal dimension on the x-axis, and visualizing the tree modifications over time as temporal edges of varying thickness. The tree hierarchy at each time step is depicted as a vertical, one-dimensional nesting relationships, similarly to standard, nontemporal treemaps. Naturally, temporal edges can cross in the visualization, decreasing readability. Heuristics were proposed to minimize such crossings in the literature, but a formal characterization and minimization of crossings in temporal treemaps was left open. In this paper, we propose two variants of defining crossings in temporal treemaps that can be combinatorially characterized. For each variant, we propose an exact optimization algorithm based on integer linear programming and heuristics based on graph drawing techniques. In an extensive experimental evaluation, we show that on the one hand the exact algorithms reduce the number of crossings by a factor of 20 on average compared to the previous algorithms. On the other hand, our new heuristics are faster by a factor of more than 100 and still reduce the number of crossings by a factor of almost three. | en_US |
| dc.description.number | 3 | |
| dc.description.sectionheaders | It's All About Time | |
| dc.description.seriesinformation | Computer Graphics Forum | |
| dc.description.volume | 43 | |
| dc.identifier.doi | 10.1111/cgf.15087 | |
| dc.identifier.issn | 1467-8659 | |
| dc.identifier.pages | 12 pages | |
| dc.identifier.uri | https://doi.org/10.1111/cgf.15087 | |
| dc.identifier.uri | https://diglib.eg.org/handle/10.1111/cgf15087 | |
| dc.publisher | The Eurographics Association and John Wiley & Sons Ltd. | en_US |
| dc.rights | Attribution 4.0 International License | |
| dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | Keywords: Temporal treemaps, crossing reduction, temporal data, algorithm engineering, computational experiments CCS Concepts: Human-centered computing → Treemaps; Graph drawings; Theory of computation → Design and analysis of algorithms | |
| dc.subject | Temporal treemaps | |
| dc.subject | crossing reduction | |
| dc.subject | temporal data | |
| dc.subject | algorithm engineering | |
| dc.subject | computational experiments CCS Concepts | |
| dc.subject | Human centered computing → Treemaps | |
| dc.subject | Graph drawings | |
| dc.subject | Theory of computation → Design and analysis of algorithms | |
| dc.title | Improving Temporal Treemaps by Minimizing Crossings | en_US |