Home » maths » graph theory » Turning a graph into a Triangulation

# Turning a graph into a Triangulation

Ok so last time we introduced the data structure for representing a triangulation of a manifold, and here we showed how to find the triangles in a graph. Today we discuss how to take a graph and turn it into the triangulation data structure.

[SPOILERS:  Of course a graph cannot tell you which triangles (in the sense of subgraphs isomorphic to $C_3$) are considered triangles (in the sense of a two dimensional simplex or disc), so we assume that all of them are. What we are actually doing in this case is recovering the 2-skeleton of the Vietoris-Rips complex of which the given graph is the 1-skeleton. So in particular, this method will call a triangle a disc and not a circle. Please don’t worry if this paragraph doesn’t make any sense to you yet, this was written retrospectively! ]

First I’ll remind you of how we find all the triangles in a graph:

```def iterate_triangles(graph):
G=graph
V=G.vertices
V.sort(key=lambda x: G.get_degree(x), reverse=True)
n=len(V)
A={}
for i in range(n):
V[i].index=i
A[V[i]]=set()
for first_vertex in V:
for second_vertex in G.get_vertex_neighbors(first_vertex):
if first_vertex.index &lt; second_vertex.index:
for third_vertex in A[first_vertex].intersection(A[second_vertex]):
yield [first_vertex.index, second_vertex.index, third_vertex.index]
```

Now we want to iterate through the triangles, make a Triangle_Node object for each one, and find out what its neighbors are. Each triangle is given to us as a list of three vertex indices, so for each pair of vertices, we use it as a key in a dictionary pointing to the triangle, that way when another triangle with one of these pairs is created, it can look up the triangle sharing that edge.

Like this:

```class Triangulation(tig.UnDirGraph, object): #Having a special class will be convenient later.
def __init__(self, **kwargs):
super(Triangulation, self).__init__(Vertex=Triangle_Node,**kwargs) # Using Triangle_Nodes.

def triangulate(graph):
G=Triangulation()
shared_edge_dict={} #This will keep track of which triangles are adjacent to which as we
for triangle in iterate_triangles(graph):
node=Triangle_Node(A=triangle[0], B=triangle[1], C=triangle[2])
node.seen_before=False #Not necessary, gets it ready for a depth first search later
#if we want to try and orientate the manifold.
def init_nodes(nodes): #To save typing this tells the triangles about its neighbors
#that we know about so far, and conversely tells its neighbors
#that it is a neighbor.

#Since there are two ways of writing the pair A,B, we put it in both ways.
#We could just use a canonical ordering of the pair, but then
#we have just traded space for time, the choice is yours.
nodes=tuple(nodes)
op_nodes=(nodes[1],nodes[0])
try: #Looks to see if we have encounter this pair of vertices before.
neighbor = shared_edge_dict[nodes]
G.create_edge([neighbor, node])
node.neighbors[nodes]=neighbor
node.number_boundary_edges -=1
node.neighbors[op_nodes]=neighbor
neighbor.neighbors[nodes]=node
neighbor.neighbors[op_nodes]=node
neighbor.number_boundary_edges -= 1 #We know this edge is not on the boundary.
except KeyError: #Haven't seen this pair of vertices before.
node.neighbors[nodes]='BOUNDARY' #This is provisional, we will overwrite this
#later if it is truly not on the boundary.
node.neighbors[op_nodes]='BOUNDARY'
shared_edge_dict[nodes] = node #Adds the pair to the dictionary of seen pairs.
nodes = [triangle[0], triangle[1]]
init_nodes(nodes)
nodes = [triangle[0], triangle[2]]
init_nodes(nodes)
nodes = [triangle[1], triangle[2]]
init_nodes(nodes)
return G
```

And we’re done! We can now take a graph of a triangulation and produce something much more useful. This part has been kind of boring, but we can use this, as you’ll see next time, to find out whether or not the manifold is orientable, extremely easily.