# An Efficient Data Retrieval Parallel Reeb Graph Algorithm
## 5 Parallelization of the Algorithm
### Computing the Reeb Graph of Each Submanifold  
The manifold \(M_{i}^{\prime}\) is, in general, homeomorphic to the manifold \(M_{i}\), since the former is obtained from the latter by slightly extending its boundary. However, in the piece-wise linear case, the extension specified in the previous section may change the topology of the manifold. This will occur when a crossing edge in \(E_{i}\) or \(E_{i-1}\) contains a critical vertex of \(f\). When this case occurs, we exclude this vertex from \(M_{i}^{\prime}\) in order to keep it homeomorphic to \(M_{i}\). Using this convention, we can assume that the Reeb graph of the restriction of \(f\) on \(M_{i}\) is identical to the Reeb graph of the restriction of the Reeb graph of \(f\) on \(M_{i}^{\prime}\).  
Computing the Reeb graphs \(R(M_{i}^{\prime},f)\) for \(M_{i}^{\prime}\), for \(1\leq i\leq k+1\), now goes, as follows. To each connected component in \(M_{i}^{\prime}\) for \(1\leq i\leq k+1\), we assign a thread and the Reeb graph \(R(M_{i}^{\prime},f)\) on the submanifold \(M_{i}^{\prime}\), which can be concurrently computed.  
An ascending path that starts at a crossing edge or ends at a crossing edge will be treated specially. We call the Reeb graph edge that corresponds to such an ascending path a crossing arc. Furthermore, if the starting or the ending edge of this ascending path is a crossing edge, then we will call the corresponding node in the Reeb graph a crossing node. Every crossing node is determined by its crossing edge. In other words, given a crossing edge, we can recover its crossing node in the graphs \(R(M_{i}^{\prime},f)\) for \(1\leq i\leq k+1\). In practice, we need to be able to do this in constant time, so we create a global map \(G\) that takes as an input a crossing edge and returns its corresponding crossing node. In the case when a single crossing edge is associated with two crossing nodes from two consecutive submanifolds, then the map \(G\) associates that edge crossing edge to the two crossing nodes (this occur when the ending edge of a crossing arc and the starting edge of the crossing arc in the consequent submanifold are the same). If the crossing edge is not associated with any crossing node, then this map returns a constant value indicating that this edge is not a starting or an ending crossing edge for any ascending path. Note that each connected component in \(\mathcal{C}_{f}\) has either two crossing edges that are associated with two crossing nodes or a single crossing edge that is associated with two crossing nodes. This map will be utilized in the gluing stage.  
Figure 12: An illustration of the gluing stage. (**a**) At this stage, two ascending paths from all submanifolds have been calculated. In the case when two consecutive submanifolds share a crossing edge, such as the case in the illustrative figure, the ascending path of the lower submanifold \(M_{1}\) gets terminated at the at a crossing edge. Similarly, an ascending path from the higher submanifold \(M_{2}\) gets initiated at a crossing edge. (**b**) A zoomed version of Figure (**a**) shows the two crossing edges that determine uniquely two nodes in the Reeb graphs \(R(M_{1},f)\) and \(R(M_{2},f)\). The fact that these two edges belong to the same connected component in the inverse image of the regular crossing value is used to glue the graphs \(R(M_{1},f)\) and \(R(M_{2},f)\) along the blue nodes to obtain the graph in Figure (**c**).