Visualizing Evolving Trees

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.


Introduction
Dynamic graph visualization is used in many fields including social networks [28], bibliometric networks [48], software engineering [14], and pandemic modeling [7]; see the survey by Beck et al. [10]. Here we focus on a special case, evolving trees. In evolving trees the dynamics are captured only by growth (whereas in general dynamic graphs, nodes and edges can also disappear). While this is a significant restriction of the general dynamic graph model, evolving trees are common in many domains including the Tree of Life [36] and the Mathematics Genealogy Graph [35]. An evolving tree can also model disease spread, where nodes correspond to infected individuals and a new node v is added along with an edge to existing node u if u infected v. Visualizing this process can help us see how the infection spreads, the rate of infection, and to identify "super-spreaders." There are several methods and tools that can be used to visualize evolving trees [2,15,16,38], however, most of them have limitations that can impact their usability in this domain. Some represent nodes only as points ignoring labels [15,16], which makes them less useful in real-life applications where it is important to see what each node represents. Others utilize the level-by-level approach for drawing hierarchical graphs [27,40], which does not capture the underlying graph structure well. Force-directed algorithms tend to better capture the underlying graph structure [31], although they may introduce unnecessary edge crossings. With this in mind, we propose two methods for drawing crossingfree evolving trees that optimize the following desirable properties: 1. Desired edge length realization: The Euclidean distance between two nodes u and v in the layout should realize the corresponding pre-specified edge length l(u, v), or be uniform when no additional information is given. This is important in several domains, e.g., when visualizing phylogenetic trees [6], where the edge length represents evolutionary distance between two species. 2. Layout compactness: The drawing area should be proportional to the total area needed for all the labels. A good visualization should have the labeled graph drawn in a compact way [39]. This prevents the trivial solution of scaling the layout until all overlaps and crossings are removed, which can create vast empty spaces in the visualization. 3. Stability: Between time steps, nodes should move as little as possible. This helps the viewer maintain a mental map of the graph [37]. If the graph moves around too much, it is difficult to see where new nodes and edges are added and we lose the context of the new node's relation to the rest of the graph.
We propose two force-directed methods that ensure no edge crossings and optimize desired edge length, compactness and stability. Minimizing edge crossings is important in graph readability [42], and since we work with trees, a layout without edge crossings is possible and desirable. We use two trees extracted from Tree of Life [36] and the Mathematics Genealogy [35] projects to demonstrate the new methods and quantitatively evaluate their performance, measuring desired edge length realization, compactness, stability, stress, crossings, and running time. We also evaluate the performance of five earlier methods, showing the two proposed methods perform well overall; see

Related Work
Dynamic graph drawing has a long history [11,46] and two broad categories: offline and online. In the easier offline setting we assume that all the data about the dynamics is known in advance. Algorithms for offline dynamic visualization use different approaches including combining all time-slice instances into a single supergraph [18][19][20], connecting the same node in consecutive time-slices and optimizing them simultaneously [22][23][24], providing animation [4], and showing small multiples type visualization [3]. DynNoSlice by Simonetto et al. [44] is one of the most recent approaches for this setting and is different from the prior methods as it does not rely on discrete time-slices.
Online dynamic graph drawing deals with the harder problem -when we do not know in advance what changes will occur. One can optimize the current view, DynNoSlice [44] DynaGraph [40] Dagre [27] Radial [49] ImPrEd [ given what has happened in the past, but cannot look into the future, as the information is not available. Cohen et al. [15,16] and Workman et al. [50] describe algorithms for dynamic drawing of trees that place nodes that are equidistant from the root on the same level (same y coordinate). These algorithms do not take edge lengths into consideration, and the hierarchical nature of the layout can lead to exponential differences between the shortest and longest edges.
DynaDAG is an online graph drawing method for drawing dynamic directed acyclic graphs as hierarchies [40]. This method moves nodes between adjacent ranks based on the median sort. It was not specifically developed 5 for trees and may introduce crossings; see Fig. 2. Other approaches for online dynamic graph drawing have maintained the horizontal and vertical position of nodes [37], used node aging methods [29], and adapted multilevel approaches [17] (using FM 3 [30]). Online approaches have also been implemented on the GPU [25]. However, these methods do not guarantee crossing-free layouts for trees and do not take into account desired edge lengths.  Dagre is a multi-phase algorithm for drawing directed graphs based on [27]. The initial phase finds an optimal rank assignment using the network simplex algorithm. Then it sets the node order within ranks by an iterative heuristic incorporating a weight function and local transpositions to reduce crossings (via the barycenter heuristic) [32]. However, since Dagre draws graphs in a hierarchical structure, the edge lengths may vary arbitrarily; see Fig. 2.
The radial layout implemented in yFiles [49] displays each biconnected component in a circular fashion 6 . Radial layouts were introduced by Kar et al. [33] for static graphs. Dougrusoz et al. [21] described an interactive tool for dynamic graph visualization based on the radial layout. Six and Tollis [45] adapted the radial idea to circular drawings of static biconnected graphs and experimentally showed that their layout has fewer edge crossings. Kaufmann et al. [34] extended this model to handle dynamic graphs, providing the basis of the yFiles radial implementation. Pavlo et al. [41] adapted the idea to make the radial layout computation parallelizable. Bachmaier [5] further improved the radial layout algorithm for static graphs by adapting the hierarchical approach [47] to minimize edge crossings. Radial layout methods have more freedom than the traditional level-by-level tree layout methods. Nevertheless, they are still constrained and can result in unstable visualization for dynamic graphs in general and evolving trees in particular; see Fig. 3.
Force-directed algorithms [18-20, 43, 44] underlie many static and dynamic graph visualization methods. Unlike hierarchical and radial approaches, forcedirected algorithms place nodes at arbitrary positions, and so tend to generate more compact layouts that better realize desired edge lengths. By adjusting forces appropriately, one can also generate stable layouts by this approach. In particular, ImPrEd, by Simonetto et al. [43], provides a force-directed approach to improve a given initial layout, without introducing new edge crossings. To the best of our knowledge, there are no force-directed methods for evolving trees.  Fig. 3: A radial layout of a 400-node evolving tree of life (a) and the layout after adding 100 nodes (b). As most of the growth occurred on the right side, it is easy to see the instability -a lot of movement was needed to accommodate it. Also, nodes are too close to each other if labeled.

Algorithms for Visualizing Evolving Trees
Here, we describe two force-directed algorithms for evolving tree visualization, DynaCola and DynaSafe, that realize desired edge lengths without creating crossings, and optimize compactness and stability. DynaCola avoids edge crossings by creating and maintaining a "collision region" for each edge. While collision detection/prevention is usually applied to nodes, by carefully applying it to the edges we can prevent all edge crossings. DynaSafe prevents edge crossings with a "safe" coordinate update at every step of the algorithm. Before updating a coordinate, it first checks whether the update will introduce a crossing and then limits the update magnitude to avoid the crossing.

DynaCola
DynaCola stands for Dynamic Collision, as the algorithm uses the collision forces to prevent edge crossings. This is a force-directed algorithm, augmented with edge-regions used to prevent crossings; see Algorithm 1 in the Appendix. Recall that we are gradually growing a tree, one node at a time, while maintaining a crossing-free layout and optimizing desirable properties (desired edge lengths, compactness, stability). The DynaCola force-directed algorithm relies on the following forces and is implemented in d3.js [12]: -A force f E for each edge, to realize the desired edge length. The strength of this force is proportional to the difference between the edge distance in the layout and the desired edge length.
-A general repulsive force f R defined for all pairs of nodes and implemented with the Barnes-Hut quad-tree data structure [8]. This helps realize the global structure of the underlying tree. -A collision force f C for each edge, described in details below. This force prevents edge crossings.
-A gravitational force f G that attracts all nodes to the center of mass. This force draws the nodes closer together and improves compactness.
To ensure that no edges cross during an update, we define a collision region around each edge: if any edge/node moves too close to another edge, it will be pushed away. To create a collision region for an edge e = (u, v), we can create collision circles with diameter equal to the length of e for both u and v. Then every point of e will be either inside the collision region of u or v. However, the sum of all collision regions for all nodes will be unnecessarily large and the layout will not be compact. With the help of subdivision nodes along the edges, we can reduce the sum of all collision regions. Let e = (u, v) be an edge in the graph. We use a set of subdivision nodes V s = {v 1 , v 2 , · · · , v k } and replace the edge We assign the desired edge length of an edge in E s equal to l(u, v)/|E s |, where l(u, v) is the desired edge length. In general, the number of subdivision nodes per edge should be a small constant n s (by default n s = 1), since the complexity of the algorithm increases as n s increases. Also, note that n s determines the number of bends per edge (no bends when n s = 0, one bend when n s = 1, and so on). Note that, the collision force does not follow any hard constraint, even after having a collision region edge crossings may happen. If existing edges introduce crossings, then we roll back to previous crossing-free coordinates.
When a new node is added to the tree, a new edge also is added, with one of its endpoints already placed. To place the new node, we randomly sample a set of 100 nearby points at a distance equal to the desired edge length, trying to find a crossing-free position. If we cannot find such a suitable point, we gradually reduce the distance and repeat the search until we find a crossing free position. Once the new node has been placed, we subdivide its adjacent edge as described above.

DynaSafe
DynaSafe stands for Dynamic Safety, as the algorithm prioritizes safe moves and will not make a move if it introduces an edge crossing, see Algorithm 2 in Appendix. DynaSafe is also a force-directed algorithm, however, it differs from DynaCola as it draws straight-line edges (rather than edges with bends). The algorithm utilizes the following forces and is implemented in d3.js [12] -A force f E for each edge that is similar to DynaCola.
-A stress-minimizing force f S on every pair of nodes not connected by an edge, used to improve global structure. The desired distance is the shortest-path distance between the pair, and the magnitude of the force is proportional to the difference between the realized and desired distance.
-A repulsive force that is similar to DynaCola.
-A gravitational force that is similar to DynaCola.
DynaSafe prevents edge crossings from occuring at any time by updating the coordinates safely: if the proposed new coordinate of a node introduces crossings, we gradually reduce the magnitude of the movement until the crossing is avoided. To place the new node, we randomly sample a set of 100 nearby points to find a crossing-free position for its adjacent edge. If we cannot find a crossing free position using the sample points, we continuously reduce the edge length until we find a crossing free position. Once the node is added, an iteration of forcedirected algorithm optimizes the layout (again without introducing crossings).
By the nature of force-directed algorithms, after one phase of force computations each node has a proposed new position. Before moving any node to its proposed new position, we check that the move is "safe," i.e., it does not introduce a crossing. If the movement of a node introduces any crossings, then the magnitude of the move is set to p% of the original movement. This is repeated (if needed) at most q times, and if the crossing is still unavoidable then the node is not moved in this phase. By default p = 0.8 and q = 12.

Experimental Evaluation
We evaluate DynaCola and DynaSafe, along with five earlier methods: Dyn-NoSlice, DynaGraph, Dagre, Radial, and ImPrEd. We use two evolving trees to visually compare the results, as well quantitatively evaluate the desired properties.

Datasets
We use two real-world datasets to extract evolving trees for our experiments.
The Tree of Life: captures the evolutionary progression of life on Earth [36]. The underlying data is a tree structure with a natural time component. As a new species evolves, a new node in the tree is added. The edges give the parent-child relation of the nodes, where the parent is the original species, and the child is the new species. We use a subset of this graph with 500 nodes. The maximum node degree of this tree is 5, and the radius is 24.
The Mathematics Genealogy: shows advisor-advisee relationships in the world of mathematics, stretching back to the middle ages [35]. The dataset includes the thesis titles, students, advisors, dates, and number of descendants. The total number of nodes is around 260,000 and is continuously updated. While this data is not quite a tree (or even connected, or planar), we extract a subset to create a tree with 500 nodes. The maximum node degree of this tree is 5 and the radius is 14.

Evaluation Metrics
We use standard metrics for each of our desired properties: desired edge length preservation, compactness, and stability. Additionally, we compute the stress of the drawing and the number of crossings. This gives a total of five quantitative measures. For each of these measures we define a loss function as follows: Desired Edge Length (DEL): To measure how close the realized edge lengths are to the desired edge lengths, we find the mean squared error between these two values. Given the desired edge lengths {l ij : (i, j) ∈ E} and coordinates of the nodes X in the computed layout, we evaluate with the following formula: This measures the root mean square of the relative error as in [1], producing a non-negative number, with 0 corresponding to a perfect realization. For DynaCola we subdivide the edges, to compute DEL, we set the length of the subdivided edges such that the summation of the length of the subdivided edges is equal to the length of the original edge.
Compactness: To measure the compactness of each layout, we use the ratio between the drawing area and the sum of the areas for all labels [9]. We assume that a label is at most 16 characters, as we abbreviate longer labels. The sum of the areas for all labels gives the minimum possible area needed to draw all labels without overlaps (ignoring any space needed for edges). The area of the actual drawing is given by the smallest bounding rectangle, once the drawing has been scaled up until there are no overlapping labels. Once we have this scaled drawing, we find the positions of the nodes with the largest and smallest x and y values (X max,0 , X min,0 , X max,1 and X min,1 ). Using these values we calculate the area of the bounding rectangle.

Compactness loss
This formula produces a non-negative number; the ideal value for this measure is 1 and corresponds to a perfect space utilization.
Stability: To measure stability, we consider how much each of the nodes moved after adding a new node. We then sum the movements of all nodes over all time steps. Since different algorithms use different amounts of drawing areas, we divide the value by the drawing area to normalize the results. This measure is similar to that used in DynNoSlice [44], but since DynNoSlice does not use time slices, it is closer to the measure found in [13]: Here, T is the maximum time (500 in our two datasets). This formula produces a non-negative number; the ideal value is 0 and corresponds to a perfectly stable layout (no movement of any already placed nodes).
Stress: This measure evaluates the global quality of the layout, looking at the differences between the realized distance between any pair of nodes and the actual distance between them. This measure is used in a variety of graph drawing algorithms [13,26,44]: Here, D i,j is the shortest path distance in the graph. This formula produces a non-negative number; the ideal value is 0 and corresponds to a perfect embedding (that captures all graph distances by the realized Euclidean distances).
Edge Crossings: Finally, we measure the number of edge crossings in each of the outputs. Note that our algorithms DynaSafe and DynaCola enforce "no edge crossings" as a hard constraint. However, DynNoSlice and DynaGraph do not have such a constraint and so can and indeed do, introduce crossings. Therefore we include the number of edge crossings for a complete comparison.

Experimental Setup
We compare these algorithms to five previous algorithms: DynNoSlice, Dyna-Graph, Dagre, Radial, and ImPrEd. We note that while Dagre, Radial, and ImPrEd are not specifically designed for dynamic graphs, they can be modified for this purpose. Specifically, we can use the layout of a tree at step i to initialize the layout of the tree at step i + 1, add the new edge, and update the layout.
We consider the simplest case for the desired edge length by using a uniform length of 100 for all edges. This is a necessary parameter for our algorithms DynaCola and DynaSafe, but only needed in the other four algorithms in order to compute the desired edge length measure. To be able to compare our methods to the other four (that do not take desired edge length into account), we set the desired edge length equal to the average edge length obtained in the layout. We then normalize these values for a fair comparison.
The performance of DynNoSlice depends heavily on two parameters, τ and δ that must be tuned. With the help of the authors, we found τ = 16 and δ = 4 worked well for our 500-node trees. The performance of ImPrEd depends on two parameters: repulsion force and the number of iterations. The default values of repulsion force and the number of iterations are equal to one and 200 respectively. We have used the default values. The larger the number of iterations is, the better the output of ImPrEd is. However, the running time increases as the number of iterations increases. We keep the number of iterations equal to 200 since it already takes more than 4 hours to compute the 500-node trees. The performance of DynaCola depends on the number of subdivision nodes n s ; we use n s = 1 for the experiments. For the radial layout algorithm, we have used the default settings in the yFiles [49] implementation. The other algorithms are also used with their default settings. We have implemented our algorithms in d3.js [12]. For other algorithms, we have used the default API. All experiments are conducted in a machine that has macOS 11.3.1 operating system, a 2.3 GHz 8-core Intel core i9 processor, and 32 GB 2667 MHz DDR4 memory.

Results
Both the visual and quantitative results indicate that the two new methods perform well overall; see Fig. 4.

Desired Edge Lengths:
The quantitative results are shown in Table 1. We use green to show the best results and yellow for the second best and indicate that DynNoSlice, DynaCola, and ImPrEd perform well. For the math genealogy 500node tree, ImPrEd is the best. However, both DynNoSlice and ImPrEd have significantly larger running times (measured in hours, rather than minutes or seconds) as discussed below. Moreover, while ImPrEd does well on the math genealogy graph, it does not do well on the tree of life graph. For the math genealogy 500-node tree, DynaCola is the second best and DynNoSlice is third. For the tree of life dataset, DynaCola is the best, DynNoSlice is the second best and DynaSafe is third. DynaGraph has the worst performance -not surprising given that it is a hierarchical layout, which is forced to use some very long edges near the root.  Table 1: Desired edge lengths of math genealogy tree (MG) and tree of life (TOL).

Compactness:
The quantitative results are shown in Table 2 and indicate that DynNoSlice outperforms the rest of the algorithms. DynaCola is second best and DynaSafe is third. Here, Dagre has the worst performance. Although DynNoSlice performs well, it introduces many edge crossings as discussed later. DynaCola layouts have higher compactness than DynaSafe. The absence of stress-related force allows placing nodes closer even if the graph theoretic distance is higher. Consider a path, the layout will be a straight line if stress is minimized. However, a zig-zag layout will provide better compactness.

Stability:
The quantitative results are shown in Table 3 and idicate that Dyna-Cola does best. DynaGraph is second, and DynaSafe is third. The radial layout performs worse in this metric because it rotates the subtrees as more edges are added.

Stress:
The quantitative results are shown in Table 4. In general, DynaSafe does much better on this measure than the rest. Again, ImPrEd performs well       methods are not as fast as the Radial algorithm and not as slow as DynNoSlice, taking about 5 minutes on the 500-node trees.Due to space limitations, we provide more details of running time in the Appendix.

Discussion and Limitations
While there are many algorithms and tools for drawing static trees, only a few can handle dynamic trees well. Among those, even fewer takes edge labels into account while also preventing edge crossings. With this in mind, we described two methods that give better, readable layouts for evolving trees. We compared these two algorithms with others that have been set up for dynamic trees. With respect to the criteria that we have put forward, our algorithms match or exceed each of these algorithms. Fully functional prototypes and videos showing them in action are available online https://ryngray.github.io/dynamic-trees/. Source code and all experimental data can be found on github https://github.com/ abureyanahmed/evolving_tree.
Naturally, our work comes with several limitations that could be addressed in future work.
Anticipating the Future: Currently, the two new methods, DynaCola and DynaSafe perform well for evolving trees, where growth is the only type of change. A natural question is whether these algorithms can be generalized to the more challenging problems of online dynamic tree visualization. Answering such question may need more precise modeling of the graph dynamics. Even though online dynamic graph drawing assumes no knowledge about the actual changes to the graph in the future, some prior knowledge of the graph may be available or predictable in advance. For example, knowing the expected depth or size of a tree or maximum degree of nodes (e.g., from domain knowledge about the specific type of graph) may help the layout algorithm reserve enough space for growth. In general, we anticipate that if one can model the evolving dynamics of the graph (e.g., probabilistically), incorporating knowledge of such dynamics into the drawing algorithm may help improve the resultant drawing; conversely, carefully defining compatible graph dynamics for a particular drawing algorithm will also allow us to identify the limitations of the given algorithm.
Multi-level Label Display: For simplicity, in this work we assume labels to be always shown in the drawing in a fixed font size. In practice, however, labels may come with different levels of importance and different desired font size. In that case, one might prefer to see only important labels displayed first in a zoomed out view of the graph, and later see more labels when zooming in. Incorporate such multi-level label display into the node placement strategy seems like an interesting and relevant problem.
Finding Desired Properties: We have proposed two different algorithms to solve the same evolving tree visualization problem, and each is associated with different benefits. Finding a continuous spectrum of algorithms with tunable parameters to balance the multiple desired properties would provide more flexibility. On the other hand, a careful human-subjects study may also help prioritize existing properties of the drawing, or help identify new desired properties from the specific tasks.
Considering More Dynamic Datasets: The datasets we considered are evolving in nature. For example, in the math genealogy dataset, once an advisee gets related to an advisor, the relationship remains forever. Although we considered only evolving trees, our ideas can be applied to datasets where the elements may get deleted. Applying the algorithms on more dynamic datasets remains future work. Fig. 1 shows a small evolving tree with labels, as obtained by the seven algorithms: DynNoSlice, DynaGraph, Dagre, Radial, ImPrEd, DynaCola, and DynaSafe. Fig. 5 shows the same layouts without the labels, allowing us to see the structure a bit better. Fig. 4 shows the layouts of the tree of life, obtained by DynNoSlice, Dy-naGraph, Dagre, Radial, ImPrEd, DynaCola and DynaSafe. Fig. 6 shows the layouts of math genealogy tree, obtained by DynNoSlice, DynaGraph, Dagre, Radial, ImPrEd, DynaCola and DynaSafe.
DynaCola performs slightly better compared to DynaSafe. However, Dyna-Cola layouts introduce bends. DynaCola layouts may be suitable where compact layouts are preferred. Since Dynasafe has better stress and does not create bends,