  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 measure 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. In this paper, we introduce a form of ordered merge
trees that does capture intrinsic order present in the data. We further define
a natural variant of the interleaving distance, the monotone interleaving
distance, which is an order preserving distance measure for ordered merge
trees. Analogous to the regular interleaving distance for merge trees, we show
that the monotone variant has three equivalent definitions in terms of two
maps, a single map, or a labelling. The labelling-based definition fairly
directly leads to an efficient algorithm for computing the monotone
interleaving distance, but unfortunately it computes only an approximation
thereof. Instead, we discover a surprising connection between the monotone
interleaving distance of ordered merge trees and the Fr\'{e}chet distance of 1D
curves. As a result, the monotone interleaving distance between two ordered
merge trees of total complexity $n$ can be computed exactly in $\tilde O(n^2)$
time. The connection between the monotone interleaving distance and the
Fr\'{e}chet distance establishes a new bridge between the fields of
computational topology/topological data analysis, where interleaving distances
are studied extensively, and computational geometry, where Fr\'{e}chet
distances are studied extensively.
