9
$\begingroup$

I would like to know if there is any notion of a discrete Riemannian metric on graphs. C. Mercat has worked on discrete Riemann Surfaces, but that's not exactly what I am working on. To be more precise, when one defines a weighted Laplacian $\Delta : \mathbb{R}^V \mapsto \mathbb{R}^V $ on a graph $G=(V,E)$ by

$$ \forall v \in V, \quad \delta (f)(v)=\sum_{w \sim v} a_{\{v,w\}} \big( f(v)-f(w) \big),$$ the family $ \big( a_{e} \big)_{e \in E}$ of reals indexed by the set of edges can be viewed as a metric on the graph. But the analogy with the case of riemannian metric on manifolds is not so obvious. For instance, what would mean that two such metrics $ \big( a_{e} \big)_{e \in E}$ and $ \big( b_{e} \big)_{e \in E}$ are conformal ? Thanks in advance, LC.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
15
$\begingroup$

One can even approximate the metric on a graph by Riemannian metrics on a 2-dim compact manifold. Namely, embed the graph into a Riemann surface, and choose a Riemann metric which gives the edge distance along the edges, and which is very small everywhere else. Then the eigenvalues of the surface Laplacian approximate the eigenvalues of the graph Laplacian. See many papers of Colin de Verdiere who used this method with great success.

Improve this answer
$\endgroup$
8
$\begingroup$

There is a very rich theory of discrete conformal equivalence on surface triangulations stemming from the following definition (attributed to Luo by the references below though see earlier work of Cooper and Rivin and see the comments for more discussion). Let $l,\tilde{l}$ be two metrics on the triangulation $T=(V,E)$, i.e. $l,\tilde{l}\in(\mathbb{R}_{>0})^E$. Then $l$ and $\tilde{l}$ are discretely conformally equivalent if:

$$\tilde{l}_{ij}=e^{(u_i+u_j)/2}l_{ij}$$

for some $u\in\mathbb{R}^V$. Compare this to the situation for two metrics $g,\tilde{g}$ on a smooth manifold $M$ which are called conformally equivalent if:

$$\tilde{g}=e^{2u}g$$

for some $u\in C^\infty(M)$.

See this paper of Bobenko, Pinkall and Springborn for a variational formulation (making this notion very "practical"; see the computer graphics papers in its references (e.g. the paper of Springborn, Schröder and Pinkall and others citing these works) and connections to circle packing, hyperbolic geometry and much more. Here's just one of the many attractive images in their paper; this one depicts a discrete conformal map between two metrics on a triangulation of a rectangle:

Figure 1 from Bobenko, Pinkall, Springborn

Note however that the natural Laplace-Beltrami operator in this setting is not the one you've written but rather the "cotangent Laplacian"; see the abovementioned paper of Springborn, Schröder and Pinkall.

I haven't looked into work on this away from the triangulation case, but I'd be very interested in it if it's out there.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ It is not due to Luo, but comes from a paper of D. Cooper and I. Rivin. Jeez. $\endgroup$
    – Igor Rivin
    Commented Dec 20, 2017 at 16:03
  • 1
    $\begingroup$ @IgorRivin Apologies for not being familiar with all of the related work and for my lack of understanding here. Luo claims that his notion of scalar curvature of distinct from the one in Cooper and Rivin, see section 1.5 of his paper arxiv.org/abs/math/0306167 . I also could not find this definition of conformal equivalence in your paper with Cooper, though perhaps you can enlighten me. $\endgroup$
    – j.c.
    Commented Dec 20, 2017 at 18:43
6
$\begingroup$

This circle of questions is studied in this old paper by D. Jakobson and I. Rivin.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .