A planar graph G = (V,E) is a graph that can be embedded in the plane, i.e. it can be drawn such that no edge crosses
with another edge. For us, this is interesting, because our meshes typically look like a two-dimensional space, or at
least can be projected locally to a two-dimensional space. What is the relation-ship between the number of vertices,
edges and faces in such a graph? A face of a graph is all of the faces induced by the graph, including the exterior
face.
Figure V F E
-----------------+---+---+---
Single point 1 1 0
Line segment 2 1 1
2 Line segments 3 1 2
Triangle 3 2 3
Quad 4 2 4
Two triangles 4 3 5
Notice that there seems to be a regularity to this. Whenever we add a line without closing the graph we add one vertex
and one edge (delta V = delta E). When we add a line using an existing vertex, we introduce a new face (delta E = delta
F). This clearly suggest the Euler-Poincare formula:
V + F = E + constant,
And looking at the above table, we find that the constant is 2 for a planar graph:
Figure V F E V+F-E
-----------------+---+---+---+-------
Single point 1 1 0 2
Line segment 2 1 1 2
2 Line segments 3 1 2 2
Triangle 3 2 3 2
Quad 4 2 4 2
Two triangles 4 3 5 2
For a mesh, we usually assume that it regular and that all faces are triangles, so F = T. We subtract the exterior face,
hence for us the constant becomes 1, and we get V + T = E + 1.
Now, what is the ratio between V, T and E? We will assume that the number of side-edges are small when compared to the
number of interior edges. We will also need the notion of half-edges and triangle vertices.
A half-edge h is a pair (e, t), where e is an edge and t is a triangle. By the above, since there are E edges, there are
close to 2*E half-edges. As a matter of fact, it is:
H = #(half-edges) = 2 * #(interior edges) + #(exterior edges) = 2 * E - #(exterior edges)
Since there are T triangles, and each triangle has 3*T half-edges, we get:
3 * T = 2 * E - #(exterior edges) =~ 2 * E
Neglecting exterior edges then, we get the ratio
T : E = 2 : 3,
Using Euler-Poincare, multiplying the equation by 2, we get:
2V + 2T = 2E + 2,
And by substituting 2E = 3T, we get:
2V = T + 2,
In other words
V:T = 1:2,
And hence we get the pleasing ratio:
V:T:E = 1:2:3.
For instance, this means that in a triangle index list, you should expect to have 6 times as many vertex indexes as you
have vertexes, because you need 3 indexes per triangle, and there’s twice as many triangles as there are vertexes.
If you’ve looked closely at a mesh, you probably have noticed that most of the vertexes are adjacent to 6 triangles. Can
we prove that?
A triangle vertex is a pair (v, t), where v is a vertex and t is a triangle. How many of these are there? Well, there’s
3 per triangle, so:
#(triangle vertexes) = 3*T = 3*(2*V) = 6*V,
So, on average, there’s 6 triangle vertexes per vertex, which means that there are on average 6 triangles adjacent to a
vertex.