# An Efficient Data Retrieval Parallel Reeb Graph Algorithm
## 1 Introduction
### Prior Work and Contribution  
Reeb graph literature is vast and it ranges from the computational accuracy of the graph to its applications in data analysis and visualization. We provide an overview here. **Reeb Graph Algorithms. ** The first provably correct algorithm to compute a Reeb graph on a triangulated surface was presented by [PERSON] and [PERSON] in [18]. They computed the Reeb graph in \(O(n^{2})\) time, where \(n\) in the number of triangles in the mesh. This time was later improved to \(O(n\log(n))\) by [PERSON] et al. [19]. Reeb graphs have also been studied for higher-dimensional manifolds and simplicial complexes. An algorithm for computing Reeb graph for a 3-manifold embedded in \(\mathbb{R}^{3}\) is proposed in [20]. The first Reeb graph algorithm on an arbitrary simplicial complex is given in [21]. This algorithm can handle a non-manifold input, but its worse case time complexity is quadratic. Reeb graph for a varying scalar function is studied in [22]. Other Reeb graphs algorithms can be found in [23; 24; 25; 17; 26]. Approximate Reeb graphs algorithms can be found in [7; 27]. However, such algorithms may lead to inaccurate results. Data retrieval from the Reeb graphs, also referred to as augmented Reeb graphs, has also been studied, and some algorithms have been presented, for instance [28; 29; 30]. A loop-free Reeb graph, which is also called a contour tree, has been used extensively in data analysis and data visualization. Algorithms for computing such graphs can be found in [21; 24; 31; 32; 33]. Contour tree have been used for scientific visualization [34], volume rendering [35], and terrain applications [36; 37]. Contour tree data retrieval is studied in [38]. For a thorough introduction to the contour tree and its applications, the reader is referred to [31; 39] and the references within. **Reeb Graph Generalizations. ** Reeb graphs have also been used to study and analyze point cloud data. The applications are numerous, including data skeletonization [28], retrieving topological information from point data such as homology group computation [40; 41], locus cut [42], data abstraction [43], and recovering structural information of a scalar function on a point data [44]. In the context of point clouds, a relatively recent construction, named Mapper [45], has received a lot of attention, as it generalizes both the Reeb graph and contour tree. Mapper has found numerous applications [46; 47; 48; 49] and it has been studied from multiple perspectives [50; 51; 52; 53]. **Applications of the Reeb Graph. ** There is a rich literature in computer graphics regarding the use of the Reeb graphs. Reeb graphs have been used in mesh segmentation [54], shape similarity [55], shape matching [56], feature-extraction [16], surface reconstruction [57], extracting tunnel and handle loops of a surface [58], removing tiny handle in an isosurface [59], and shape matching [27]. Also see [30] for further applications of Reeb graph in computer graphics. **Parallelization of Topological Structures. ** The demand to compute large data sets has increased in the last decade and, hence, the consideration of topological computations parallelization. Multiple attempts have been made in this direction, including multicore homology computation [60], spectral sequence parallelization [61], distributed contour tree [38; 62], distributed merge tree [63], alpha complexes [64], and distributed Mapper [65]. **Contributions. ** In this paper, we give a parallel Reeb graph algorithm on arbitrary triangulated mesh with and without a boundary. We prove the correctness of our method while using fundamental theorems in Morse Theory. Moreover, we discuss the performance results that compare our approach to a reference sequential Reeb graph algorithm [26]. We then show how we can use the Reeb graph to retrieve certain curves on the manifold. Finally, we utilize the data retrieval aspect of our algorithm and give an application to surface segmentation. Specifically, this article has the following contributions:  
1.