In a project I am working on, we are looking at multiple different (optimal with respect to some cost measure) triangulations of a fixed pointset $S$. I would like to cluster similar triangulations.
My first Idea was something like the edge flip distance, i.e. the minimal number of edge-flips in a quadrilateral needed to get from one triangulation to the other. Calculating this number is Np-Hard and since my datasets are not small, there are no algorithms that can calculate the flip distance in reasonable time.
Next I had a look at similarity measures for geometric graphs, but they emphasize the translation and insertion/deletion of points to get from one graph to the other one. These kinds of modifications are not interesting in my case, since the positions of the vertices are fixed for both triangulations.
In the figure two different triangulations on the same pointset are given. Note that we already have a one to one correspondence between the vertices of the two Triangulations, since they are generated with respect to the same set of points.
All in all I would like to know if there are any known similarity measures in the context of graphs/geometric graphs/triangulations, that may be interesting and could possibly be adapted to triangulations.