# Speaker: Jack Cheng

##
Title:
A Randomized O(m log n) Algorithm for Computing Reeb Graphs of
Arbitrary Simplicial Complexes

Presenting a paper by William Harvey, Yusu Wang, and Rephael Wenger

Abstract: In this paper, we present the first sub-quadratic algorithm
to compute the Reeb graph for a function
on an arbitrary simplicial complex K. Our algorithm is randomized
with
an expected running time
O(m log n), where m is the size of the 2-skeleton of K (i.e, total
number of vertices, edges and triangles),
and n is the number of vertices. This presents a significant
improvement over the previous \Theta(mn) time
complexity for arbitrary complex, matches (although in expectation
only) the best known result for the
special case of 2-manifolds, and is faster than current algorithms
for
any other special cases (e.g, 3-manifolds). Our algorithm is also very simple to implement.
Preliminary experimental results show that
it performs well in practice.