In this paper, we prove a variant of the Burger-Brooks transfer principle which, combined with recent eigenvalue bounds for surfaces, allows to obtain upper bounds on the eigenvalues of graphs as a function of their genus. More precisely, we show the
existence of a universal constants $C$ such that the $k$-th eigenvalue $lambda_k^{nr}$ of the normalized Laplacian of a graph $G$ of (geometric) genus $g$ on $n$ vertices satisfies $$lambda_k^{nr}(G) leq C frac{d_{max}(g+k)}{n},$$ where $d_{max}$ denotes the maximum valence of vertices of the graph. This result is tight up to a change in the value of the constant $C$, and improves recent results of Kelner, Lee, Price and Teng on bounded genus graphs. To show that the transfer theorem might be of independent interest, we relate eigenvalues of the Laplacian on a metric graph to the eigenvalues of its simple graph models, and discuss an application to the mesh partitioning problem, extending pioneering results of Miller-Teng-Thurston-Vavasis and Spielman-Tang to arbitrary meshes.
We address the problem of curvature estimation from sampled compact sets. The main contribution is a stability result: we show that the gaussian, mean or anisotropic curvature measures of the offset of a compact set K with positive $mu$-reach can be
estimated by the same curvature measures of the offset of a compact set K close to K in the Hausdorff sense. We show how these curvature measures can be computed for finite unions of balls. The curvature measures of the offset of a compact set with positive $mu$-reach can thus be approximated by the curvature measures of the offset of a point-cloud sample. These results can also be interpreted as a framework for an effective and robust notion of curvature.
