Merge trees are a popular topological descriptor for scalar field data. A common measure to compare two merge trees is the interleaving distance, which relies on a mapping between the two merge trees, also referred to as an interleaving. Despite its desirable properties, the interleaving distance has not been used much in practice, largely due to the fact that computing the exact interleaving distance is NP-hard. In this paper, we show that the exact interleaving distance can be computed efficiently for merge trees encountered in practice: we present the first implementation of the exact fixed-parameter tractable (FPT) algorithm by Touli and Wang [Touli and Wang, 2022]. This algorithm uses a dynamic program to test if a specific interleaving distance δ is feasible. They bound the running time using a parameter τ that captures the number of mapping options between the two merge trees for the output distance δ. Our experiments show that, even though τ can become quite large for real-world merge trees, the running time of our implementation does not depend very heavily on τ. Furthermore, we modify the FPT algorithm into a sweepline algorithm that runs much faster in practice. Finally, we introduce a natural restriction for the interleaving distance capturing the geometric similarity between the underlying scalar fields. This restricted interleaving distance can be computed more efficiently and can, in some settings, also result in more meaningful interleavings. We extend our implementations to support these restrictions and demonstrate their effect on the running time of the algorithms.

Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner.In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets.

Merge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance for comparing merge trees. However, the interleaving distance for merge trees is solely based on the hierarchical structure, and disregards any other geometrical or topological properties that might be present in the underlying data. Furthermore, the interleaving distance is NP-hard to compute.