Loops in Reeb Graphs of 2-Manifolds

Given a Morse function f over a 2-manifold with or without boundary, the Reeb graph is obtained by contracting the connected components of the level sets to points. We prove tight upper and lower bounds on the number of loops in the Reeb graph that depend on the genus, the number of boundary components, and whether or not the 2-manifold is orientable. We also give an algorithm that constructs the Reeb graph in time O(n log n), where n is the number of edges in the triangulation used to represent the 2-manifold and the Morse function.     

Persistence Approximation Property for Maximal Roe Algebras

Persistence approximation property was introduced by Hervé Oyono-Oyono and Guoliang Yu. This property provides a geometric obstruction to Baum-Connes conjecture. In this paper, the authors mainly discuss the persistence approximation property for maximal Roe algebras. They show that persistence approximation property of maximal Roe algebras follows from maximal coarse Baum-Connes conjecture. In particular, let X be a discrete metric space with bounded geometry, assume that X admits a fibred coar...     

Approximation of 3-Edge-Coloring of Cubic Graphs

The problem to find a 4-edge-coloring of a 3-regular graph is solvable in polynomial time but an analogous problem for 3-edge-coloring is NP-hard. We study complexity of approximation algorithms for invariants measuring how far is a 3-regular graph from having a 3-edge-coloring. We prove that it is an NP-hard problem to approximate such invariants by a power function with exponent smaller than 1.     

The Genus of a Digital Image Boundary Is Determined by Its Foreground,Background, and Reeb Graphs

We prove that the genus of the boundary of a digital image is precisely half of the sum of the cycle ranks of three particular graphs: the "foreground graph" and "background graph," which capture topological information about the digital image and its complement, respectively, and the Reeb graph, relative to the natural height function, associated with the digital image's boundary. We prove several additional results, including a characterization of when the cycle rank of the Reeb graph fails to equal the genus of the digital image's boundary (which can happen by virtue of the failure of the natural height function on the boundary of the digital image to be a Morse function).     

Primal-Dual Approximation Algorithms for Feedback Problems in Planar Graphs

Received: August 22, 1996     

Reeb posets and tree approximations

A well known result in the analysis of finite metric spaces due to Gromov says that given any metric space $(X,d_X)$ there exists a tree metric $t_X$ on $X$ such that ${|d_X-t_X|}_{\infty }$ is bounded above by twice $\mathrm{hyp}\left(X\right)\cdot log\left(2\left|X\right|\right)$. Here $\mathrm{hyp}\left(X\right)$ is the hyperbolicity of $X$, a quantity that measures the treeness of 4-tuples of points in $X$. This bound is known to be asymptotically tight.We improve this bound by restricting ourselves to metric spaces arising from filtered posets. By doing so we are able to replace the cardinality appearing in Gromov’s bound by a certain poset theoretic invariant which can be much smaller thus significantly improving the approximation bound.The setting of metric spaces arising from posets is rich: For example, every finite metric graph can be induced from a filtered poset. Since every finite metric space can be isometrically embedded into a finite metric graph, our ideas are applicable to finite metric spaces as well.At the core of our results lies the adaptation of the Reeb graph and Reeb tree constructions and the concept of hyperbolicity to the setting of posets, which we use to formulate and prove a tree approximation result for any filtered poset.     

Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs

In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of Bǎdoiu et al. (Proceedings of the eighteenth annual ACM–SIAM symposium on discrete algorithms (SODA 2007), pp. 512–521, 2007) and Bǎdoiu et al. (Proceedings of the 11th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2008), Springer, Berlin, pp. 21–34, 2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of a metric relaxed minor and show that if G contains an α-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is ≥α. Then, for H=K _2,3, we present an algorithm which either finds an α-relaxed minor, or produces an O(α)-embedding into an outerplanar metric.     

Reeb graph and quasi-states on the two-dimensional torus

This note deals with quasi-states on the two-dimensional torus. Quasistates are certain quasi-linear functionals (introduced by Aarnes) on the space of continuous functions. Grubb constructed a quasi-state on the torus, which is invariant under the group of area-preserving diffeomorphisms, and which moreover vanishes on functions having support in an open disk. Knudsen asserted the uniqueness of such a quasi-state; for the sake of completeness, we provide a proof. We calculate the value of Grubb’s quasi-state on Morse functions with distinct critical values via their Reeb graphs. The resulting formula coincides with the one obtained by Py in his work on quasi-morphisms on the group of area-preserving diffeomorphisms of the torus. Included is a short introduction to the link between quasi-states and quasi-morphisms in symplectic geometry.     

Reeb orbits trapped by Denjoy minimal sets

Let φ be any flow on T ⁿ obtained as the suspension of a smooth diffeomorphism of \({T^{n-1}}\) , and let \({\mathcal {A}}\) be any compact invariant set of φ. We realize \({(\mathcal{A}, \varphi|_{\mathcal{A}})}\) up to reparametrization as an invariant set of the Reeb flow of a contact form on \({\mathbb{R}^{2n+1}}\) equal to the standard contact form outside a compact set and defining the standard contact structure on all of \({\mathbb{R}^{2n+1}}\) . This uses the method from Geiges, Röttgen, and Zehmisch.     

The Reeb Graph Edit Distance is Universal

Foundations of Computational Mathematics - We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are...