Constructing the Data Structure:
First of all, to make things simpler, we enclose the whole triangulation in a large enough triangle in such a way that none of its edges intersect the others.
This will represent the outter face (labeled here as "O"):

We take the obtained graph and we process it in the following way:
- We find an independent set of vertices with degree less than or equal to 8 inside the hull:

- We remove them from the graph, obtaining independent holes:

- We retriangulate these holes (by following the same rule for labels as before):

- We repeat the above steps until we are left with 3 vertices (the large triangle).