Interleaving Reeb Graphs

In this section we define the interleaving distance of Reeb graphs due to de Silva, Munch, and Patel (2016). Strictly speaking it is somewhat misleading to name this the interleaving distance of Reeb graphs because we are not comparing the Reeb graphs directly, instead we compare what we name the Reeb precosheaf[3]. de Silva, Munch, and Patel (2016) discuss very thoroughly, why we may do this and later they also translate this into a more geometric comparison of Reeb graphs. We define this Reeb precosheaf somewhat differently from the way it is defined in this article. Using the notion of an intersection-based space we may say that de Silva, Munch, and Patel (2016) define the Reeb precosheaf as a precosheaf on the intersection-based space, that has the real numbers as an underlying set and the open intervals as distinguished open subsets. We will use a different space, but all of the distinguished open subsets of this space, except for three, can be identified with an open interval. Now because precosheaves are just functors on the distinguished open subsets, this is pretty much the same data. And the reason we can’t identify all distinguished open subsets with an interval is that we work with \(\overline{{\mathbb{R}}}\) instead of \({\mathbb{R}}\), in some sense \(\overline{{\mathbb{R}}}\) has three more open intervals than \({\mathbb{R}}\). Now we begin with defining this intersection-based space.

  • Definition. We define \(\overline{{\mathbb{R}}}_{\infty}\) to be the space that has \(\overline{{\mathbb{R}}}\) as an underlying set and \(\{\overline{{\mathbb{R}}}\} \cup \{(a, \infty] ~ | ~ a \in \overline{{\mathbb{R}}}\}\) as it’s intersection-base.

    Similarly we define \(\overline{{\mathbb{R}}}_{-\infty}\) to be the space with the same underlying set and \(\{\overline{{\mathbb{R}}}\} \cup \{[-\infty, b) ~ | ~ b \in \overline{{\mathbb{R}}}\}\) as it’s intersection-base.

    Finally we set \({\overline{{\mathbb{E}}}}:= \overline{{\mathbb{R}}}_{\infty} \times \overline{{\mathbb{R}}}_{-\infty}\) and \(\overline{D} := {\{(x, y) \in {\overline{{\mathbb{E}}}}~|~ x \leq y\}}\).

We note that any functor from the category of topological spaces to the category of sets defines a precosheaf on any topological space \(X\), since we may equip any open subset \(U \subseteq X\) with the subspace topology and since inclusions of subsets are continuous with respect to this topology. In the following definition we define a functor on the category of topological spaces and in this way also a precosheaf on any topological space.

  • Definition. For topological space \(X\) we define \(\Lambda(X)\) to be the set of connected components of \(X\).

    For a continuous map \(\varphi \colon X \rightarrow Y\) we define \(\Lambda(\varphi)\) to be the induced map from \(\Lambda(X)\) to \(\Lambda(Y)\).

Now let \(f \colon X \rightarrow \overline{{\mathbb{R}}}\) and \(g \colon Y \rightarrow \overline{{\mathbb{R}}}\) be continuous functions, let \(\varphi \colon f \rightarrow g\) be a homomorphism in the category of \(\overline{{\mathbb{R}}}\)-spaces, and let \(\Delta \colon \overline{{\mathbb{R}}} \rightarrow \overline{D}, t \mapsto (t, t)\). For a distinguished open subset \(U \subseteq \overline{D}\) let \(\varphi |_{(\Delta \circ f)^{-1} (U)} \colon (\Delta \circ f)^{-1} (U) \rightarrow (\Delta \circ g)^{-1} (U)\) be the restriction of \(\varphi\) to \((\Delta \circ f)^{-1} (U)\).

  • Definition (Reeb Precosheaf). We set \(\mathcal{C} f := (\Delta \circ f)_* \Lambda\) and name this the Reeb precosheaf of \(f\).

    Moreover we define a homomorphism \(\mathcal{C} \varphi\) from \(\mathcal{C} f\) to \(\mathcal{C} g\). For a distinguished open subset \(U \subseteq \overline{D}\) we set \((\mathcal{C} \varphi)_U := \Lambda \big(\varphi |_{(\Delta \circ f)^{-1} (U)}\big)\).

With these definitions \(\mathcal{C}\) defines a functor from the category of \(\overline{{\mathbb{R}}}\)-spaces to the category of set-valued precosheaves on \(\overline{D}\). Now assume that \(g\) is a constructible \(\overline{{\mathbb{R}}}\)-space[4]. We discuss the relationship of the Reeb graph \(\mathcal{R} g\) and the Reeb precosheaf \(\mathcal{C} g\).

  1. Lemma. The homomorphism \((\mathcal{C} \circ \pi)_g\) from \(\mathcal{C} g\) to \(\mathcal{C} \mathcal{R} g\) is an isomorphism of precosheaves.

The previous lemma implies that the isomorphism class of \(\mathcal{C} g\) is determined by \(\mathcal{R} g\). Next we will see that the converse is also true.

  1. Lemma. Let \(\beta \colon \mathcal{C} f \rightarrow \mathcal{C} g\) be a homomorphism of precosheaves, then there is a unique homomorphism \(\alpha \colon f \rightarrow \mathcal{R} g\) of \(\overline{{\mathbb{R}}}\)-spaces such that the diagram \[ \xymatrix@+=3pc{ \mathcal{C} f \ar[d]_{\mathcal{C} \alpha} \ar[dr]^{\beta} \\ \mathcal{C} \mathcal{R} g & \mathcal{C} g \ar[l]^{(\mathcal{C} \circ \pi)_g} } \] commutes.

  • Remark. One can rephrase the previous lemma in the terminology of category theory in the following way. The homomorphism \((\mathcal{C} \circ \pi)_g^{-1}\) yields a representation of the contravariant functor \({\operatorname{Hom}}(\mathcal{C} \_, \mathcal{C} g)\). A vast generalization of this statement has been provided by Funk (1995).

The previous two lemmata have the following

  • Corollary. The map \[\mathcal{C} (\_) \colon {\operatorname{Hom}}(f, \mathcal{R} g) \rightarrow {\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} \mathcal{R} g), \alpha \mapsto \mathcal{C} \alpha\] is a bijection.

  • Proof. First we note that the post-composition \((\mathcal{C} \circ \pi)_g^{-1} \circ (\_)\) yields a bijection from \({\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} \mathcal{R} g)\) to \({\operatorname{Hom}}(\mathcal{C} f, \mathcal{C} g)\). Now the previous lemma states that the composition \((\mathcal{C} \circ \pi)_g^{-1} \circ \mathcal{C} (\_)\) is a bijection as well. Thus also \(\mathcal{C} (\_)\) is a bijection.

  1. Corollary. The functor \(\mathcal{C}\) is full and faithful on the full subcategory of Reeb graphs of constructible \(\overline{{\mathbb{R}}}\)-spaces.

The previous corollary implies that the isomorphism class of \(\mathcal{R} g\) is determined by the isomorphism class of \(\mathcal{C} \mathcal{R} g\) and this class in turn is determined by \(\mathcal{C} g\), hence \(\mathcal{C} g\) determines the isomorphism class of \(\mathcal{R} g\).

In summary we may associate to any \(\overline{{\mathbb{R}}}\)-space a set-valued precosheaf, the Reeb precosheaf. In the following subsection we define two interleaving distances for set-valued precosheaves on \(\overline{D}\). And for constructible \(\overline{{\mathbb{R}}}\)-spaces we may also refer to the interleaving distances of the Reeb precosheaves as interleaving distances of Reeb graphs. This is justified by the fact that de Silva, Munch, and Patel (2016) also define an interleaving distance of Reeb graphs, that is equal to the interleaving distance of the Reeb precosheaves for constructible \(\overline{{\mathbb{R}}}\)-spaces.



[3] de Silva, Munch, and Patel (2016) actually name it the Reeb cosheaf, because in their setup, using locally connected spaces, it always is a cosheaf, a precosheaf with further properties.

[4] see the first appendix for our definition of a constructible \(\overline{{\mathbb{R}}}\)-space