It seems rather well known that given a Laplace-Beltrami operator $\mathcal{L}_{M}$ on a manifold $M$ we can approximate its spectrum by that of a graph Laplacian $L_{G}$ for some $G$ (where $G$ is usually a triangulation of $M$). See here or here for details.

What I am interested in is going in the opposite direction. That is:

Given a fixed (finite) graph $G$ is there a way to approximate its Laplacian $L_{G}$ by the Laplace-Beltrami operator $\mathcal{L}_{M}$ of some surface $M$?

The motivation for this is that if $G$ is a sufficiently dense grid, then I can take $M=\mathbb{R}^{2}$. Now suppose I add an edge to $G$ - it feels right that there should be a way to modify $M=\mathbb{R}^{2}$ into some new $M^{'}$ by somehow folding the manifold appropriately.


Yes, embed the graph into a compact Riemannian surface with a Riemannian metric which is concentrated near the embedded praph and induces the graph distances on the graph. Away from a tubular neighborhood of the graph the metric should be uniformly small. Then the Laplace Beltrami operator of the the surface approximates the graph Laplacian. This method was used by Yves Colin de Verdiere many times. See for example:

  • MR0932800 (90d:58156)
    Colin de Verdière, Yves(F-GREN-F) Construction de laplaciens dont une partie finie du spectre est donnée. (French) [Construction of Laplacians for which a finite subset of the spectrum is given] Ann. Sci. École Norm. Sup. (4) 20 (1987), no. 4, 599–615.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.