Propagate And Pair: A Single-Pass Approach To Critical Point Pairing In Reeb Graphs

With the popularization of Topological Data Analysis, the Reeb graph has found new applications as a summarization technique in the analysis and visualization of large and complex data, whose usefulness extends beyond just the graph itself. Pairing critical points enables forming topological fingerprints, known as persistence diagrams, that provides insights into the structure and noise in data. Although the body of work addressing the efficient calculation of Reeb graphs is large, the literature on pairing is limited. In this paper, we discuss two algorithmic approaches for pairing critical points in Reeb graphs, first a multipass approach, followed by a new single-pass algorithm, called Propagate and Pair.

Junyi Tu, Mustafa Hajij, and Paul Rosen. Propagate And Pair: A Single-Pass Approach To Critical Point Pairing In Reeb Graphs. International Symposium on Visual Computing, 2019.

@article{tu2019propagate,
  title = {Propagate and Pair: A Single-Pass Approach to Critical Point Pairing in Reeb
    Graphs},
  author = {Tu, Junyi and Hajij, Mustafa and Rosen, Paul},
  journal = {International Symposium on Visual Computing},
  year = {2019},
  abstract = {With the popularization of Topological Data Analysis, the Reeb graph has
    found new applications as a summarization technique in the analysis and visualization of
    large and complex data, whose usefulness extends beyond just the graph itself. Pairing
    critical points enables forming topological fingerprints, known as persistence diagrams,
    that provides insights into the structure and noise in data. Although the body of work
    addressing the efficient calculation of Reeb graphs is large, the literature on pairing
    is limited. In this paper, we discuss two algorithmic approaches for pairing critical
    points in Reeb graphs, first a multipass approach, followed by a new single-pass
    algorithm, called Propagate and Pair.}
}