An Interleaving Distance for Ordered Merge Trees

Merge trees are a common topological descriptor for data with a hierarchical component. The
interleaving distance, in turn, is a common distance measure for comparing merge trees. In this
abstract, we introduce a form of ordered merge trees and extend the interleaving distance to a
measure that preserves orders. Exploiting the additional structure of ordered merge trees, we then describe an O(n2) time algorithm that computes a 2-approximation of this new distance with an additive term G that captures the maximum height differences of leaves of the input merge trees.