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](https://mathoverflow.net/questions/66892/is-the-laplacian-on-a-manifold-the-limit-of-graph-laplacians) or [here](http://arxiv.org/abs/1301.2222) 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.



Can the graph Laplacian be well approximated by a Laplace-Beltrami operator?
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.


