Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an n-cycle has χ = 0 and K4 has χ = –2.
Is there an analog for the Gauss-Bonnet theorem for graphs, something akin to:
     [total turn angle] + [enclosed curvature] = τ + ω = 2 π χ ?
Certainly if one embeds the graph on a manifold, then an interpretation is possible via Gauss-Bonnet on the manifold. But is there a more purely combinatorial interpretation?

Addendum. (27Nov11). A new paper on this topic just appeared on the arXiv: Oliver Knill (who answered below back in March), "A graph theoretical Gauss-Bonnet-Chern Theorem." arXiv:1111.5395v1. Here is Knill's first figure:
     Knill Fig 1

share|improve this question
    
When you say "embeds the graph in a manifold", do you mean "embeds the graph in a compact surface so that its complement is a disjoint union of disks"? I am having trouble seeing how this would work in a more general situation. –  S. Carnahan May 28 '10 at 14:49
    
Yes, that is what I meant, your precision is much preferable to my off-hand way of expressing it. –  Joseph O'Rourke May 28 '10 at 15:09
    
@Joseph: Are you explicitly interested in general graphs - including trees or the graph shown above - or is it OK to consider specific families of graphs, e.g. polyhedral graphs? (I believe that it is possible to have a purely combinatorial interpretation of Gauss-Bonnet for polyhedral graphs, independent of a specific embedding.) –  Hans Stricker Jan 22 '13 at 15:37
add comment

3 Answers

up vote 16 down vote accepted

One can do the following : given a graph with $n$ vertices and $m$ edges, define the scalar curvature of a vertex $x$ of valency $v(x)$ by $S(x)=2-v(x)$. Isolated and pendant vertices have positive scalar curvature, $S$ vanishes precisely on degree two vertices (wich are those one want to call flat), and is negative for higher degrees, reminiscent of the trees being $\mathrm{CAT}(-\infty)$.

Now $\sum_x S(x)=2n-\sum_x v(x)=2\chi$ is a Gauss-bonnet formula. It is very simple, but one does not expects much more from such local considerations.

I guess that to get a more subtle formula, one can try to add some geometric structure to the graph (for example, a length on each edge and an angle for each pair of adjacent edges, and maybe a circular ordering of the edges incident to each vertex).

share|improve this answer
    
Very nice! Thanks! Presumably, then, there is a version for, say, a simple cycle in the graph enclosing a certain amount of "scalar curvature." –  Joseph O'Rourke May 28 '10 at 14:51
    
I like this answer! Intuitively a negative curvature point is one with 'more space than one might expect around it' and a positive curvature point is one with less. Ties up quite nicely I think... –  Tom Boardman May 28 '10 at 15:55
add comment

There is indeed a version of Gauss-Bonnet for graphs $G$ embedded on a 2-manifold. Here, the combinatorial curvature at a vertex $x$ of $G$ is

$1-\frac{deg(x)}{2} + \sum_{f \sim v} \frac{1}{size(f)}$,

where $f \sim v$ means that the face $f$ is incident to the vertex $x$.

This paper by Chen and Chen, then gives a Gauss-Bonnet formula for embedded infinite graphs with a finite number of accumulation points.

share|improve this answer
add comment

There are different type of curvatures for graphs. In two dimensions its not the degree of the point which matters but the length of the circles at the point like in differential geometry. This is different from the degree if graphs with boundary are considered. The simplest curvature for two dimensional graphs (I defined the dimension for graphs in http://arxiv.org/abs/1009.2292). For the curvature K(x) = 6-|S(x)|, any two dimensional graph G has total curvature 6 chi(G). More interesting and subtle is a second order curvature 2|S1(x)|-|S2(x)| which is differential geometrically motivated because curvature is a second order difference notion. Gauss-Bonnet is now not true in general and it seems that some smoothness condition needs to be satisfied. It is true for all two dimensional graphs non-negative curvature and for graphs which are "smooth" enough in some sense which I still struggle to define. I myself got more interested in Gauss-Bonnet-Chern for n-dimensional graphs and have a result there. There is a natural Chern-Euler form on n-dimensional graphs those total sum is the Euler characteristic for an n-dimensional graph. This form is defined also in odd dimensions but seems to be zero (it is in 3 dimensions but I still struggle to verify this in higher dimensions). Note that all this is purely graph theoretical. No additional structure on the graph is necessary. No embedding in an ambient Euclidean space necessary for example. The inductive dimension as defined in the above mentioned paper (revised here: http://www.math.harvard.edu/~knill/graphgeometry/papers/1.pdf) is a natural way to define polyhedra and polytopes as graphs which become n-dimensional graphs after some truncation or stellation procedure. The inductive dimension for graphs looks similar to inductive dimension usually considered in topology but is utterly different. With the usual inductive dimension, any graph would be one dimensional.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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