Triangulation

[Gordon Royle]

You have to be a bit careful because there are a number of different  
meanings of the word "triangulation" - sometimes computational  
geometry people start with a convex polygon and then want to connect  
the existing vertices, without using any more.

For graph theorists, a (planar) triangulation is a graph embedded in  
the plane where every face is a triangle.

Any such graph has n vertices, 3n-6 edges and by Euler's relation (E-V 
+F=2) we get 2n-4 triangular faces.

BUT, there can be triangles that are not faces - these are usually  
called "separating triangles" or "non-facial triangles".

My guess is that the maximum number of such triangles occurs in  
graphs that are constructed in the following fashion:

     - start with K_4 (4 vertices, 4 triangles)
     - insert a vertex into a face, joining it to all three vertices  
of that face, thus creating one new vertex and 3 new triangles - 5  
vert, 7 triangles
     - repeat the process, creating one extra non-facial triangle per  
step

Total is n vertices, 2n-4 + (n-4) = 3n - 8 triangles...  I am pretty  
sure that this is the correct answer.

This collection of graphs is interesting because they are the  
uniquely 4-colourable planar graphs.

Cheers

Gordon

>
>> What is the maximum number of triangles of a triangulation  
>> connecting N
>>
> nodes in a plane?
>
>>
>> (needed as upper memory bound for triangulation in CalculiX,
>>
> www.calculix.de)