Loops in Reeb graphs of 2-manifolds (Q1762948)

Let \(N\) be a compact connected surface of genus \(g\) with \(h\) boundary components and let \(f\) be a Morse function on \(N\). The Reeb graph of \(f\) is obtained from \(N\) by contracting the connected components of the level sets to points. The authors obtain sharp upper and lower bounds for the number of loops in the Reeb graph that depend on \(g\), \(h\) and the orientability of \(N\). The main result can be summarized as follows: When \(N\) is orientable, the number of loops is equal to \(g\) if \(h=0\) and is between \(g\) and \(2g+h-1\) if \(h\geq 1\); when \(N\) is nonorientable the number of loops is between \(0\) and \(g/2\) if \(h=0\), and is between \(0\) and \(g+h-1\) if \(h\geq 1\). The authors also give an algorithm for the construction of the Reeb graph in time O\((n \log n)\), where \(n\) is the number of edges in the triangulation used to represent the surface and the Morse function.