# An Efficient Data Retrieval Parallel Reeb Graph Algorithm
## 4 Reeb Graph Sequential Algorithm on Triangulated Surfaces
### Correctness of the Sequential Algorithm  
For a function \(f:M\longrightarrow[a,b]\) and \(c\in\mathbb{R}\) define:  
\[M_{c}:=\{x\in M|f(x)\leq c\}.\]  
Note that we allow \(M_{c}\) to be empty. Moreover, we define:  
\[M_{[c,d]}:=\{x\in M|c\leq f(x)\leq d\}.\]  
The correctness of our algorithm relies on the following two facts:  
1. The only topological changes to the level sets of \(f\) occur when as pass a critical point. This is formally stated in Theorem 1. 2. The structure of the manifold around a critical point is completely determined by the index of that critical point. We give this in Theorem 2. The proof of Theorems 1 and 2 can be found in [69]. **Theorem 1**. : _Let \(f:M\longrightarrow[a^{\prime},b^{\prime}]\) be a smooth function on a smooth surface \(M\). For two reals \(a,b\) with \(a^{\prime}<a<b<b^{\prime}\), if \(f\) has no critical values in the interval \([a,b]\), then the surfaces \(M_{a}\) and \(M_{b}\) are homeomorphic._  
The above algorithm relies on Theorem 1. Namely, as we trace an ascending path, we assume that no topological change occurs until we reach the next critical point. The ascending path may not terminate at the next critical point, provided the part of the manifold in which this path is traveling in has not changed its topology. This will become more evident after we provide the next theorem, which shows the exact structure of \(M_{[c,d]}\) around a critical point. **Theorem 2**. : _Let \(M\) be a compact connected surface, possibly with a boundary, and let \(f:M\longrightarrow[a,b]\) be a Morse function on \(M\). Let \(p\) be a critical point and let \(t\) be its corresponding critical value. Let \(\epsilon>0\) be small enough, so that \(I_{\epsilon}:=[\epsilon-t,\epsilon+t]\) has only the critical value \(t\)._  
1. _If_ \(index(p)\) _is equal to 0 or 2, then_ \(M_{I_{\epsilon}}\) _is homeomorphic to a disjoint union of a disk and a finite number of topological cylinders (that is a genus zero surface with two boundary components)._
2. _If_ \(index(p)=1\)_, then_ \(M_{I_{\epsilon}}\) _is homeomorphic to a pair of pants and a finite number of topological cylinders._  
The previous two theorems show that for a given Morse \(f\) function on \(M\), we can arrange \(M\) so that at each critical point, only a single topological event occurs, and this topological event occurs around the critical point. Moreover, we know exactly what topological event occurs by considering the index of the critical point. Figure 8 illustrates this. Moreover, subcomplex \(X_{M,f}\) constructed in the algorithm has the same Reeb graph structure of that of \(M\) around the critical points. See Figure 10.  
This shows that any two-manifold can be built from the building blocks in Figure 9. Moreover, Theorem 2 shows that the restriction of \(f\) on \(M_{I_{\epsilon}}\) has the shapes that are given in Figure 10.  
Figure 8: Given a Morse function \(f\) on a surface \(M\), we can slice \(M\), so that, around each critical value \(t\), the submanifold \(M_{[t-\epsilon,t+\epsilon]}\) is a disjoint union of simple building blocks: pair of pants, topological cylinders, and topological disks. In other words, this gives us the structure of the Reeb graph around an interval \(I_{e}\) that contains a single critical value. Now, let \(e=(p,q)\) be an edge in a Reeb graph \(R(M,f)\) connecting between the two nodes \(p\) and \(q\), which correspond to critical points of \(f\). For each such edge, we can find a preimage arc \(E\) in \(M\) that is mapped to \(R(M,f)\) via the map \(\pi:M\longrightarrow R(M,f)\). The preimages of the value \(p\) and \(q\) under \(\pi\) are the critical set \(C_{p}\) and \(C_{q}\) in \(M\), respectively. Hence, each arc \(E\) must start at a point \(A\) in \(C_{p}\) and end at a point in \(B\) in \(C_{q}\). Each arc on \(M\) characterizes the edge \(e\). An ascending path that is constructed in the sequential algorithm essentially traces an arc in the way described above.