A polygon $P\_k$ divided by $k-2$ diagonals into triangles is called a polygonal triangulation. These are the vertices of the triangulation graph $\mathcal P\_k$. Two vertices are connected by an edge if one triangulation is obtained from another by the *diagonal flip*, i.e. we take two triangles of the triangulation that share a side, and in their union (where that side is a diagonal), replace that diagonal by the other diagonal. Sleator, Tarjan, and Thurston proved that the diameter of the
triangulation graph ${\mathcal P}\_k$ is bounded above by $2k-10$. Hence the problem of finding a shortest path in that graph between two triangulations is in NP. 


 **Question 1.**  Is it in P? 


 **Question 2.**  What is known about the complexity of finding the shortest path in the triangulation graph of other surfaces?


 **Update.**  I have posted a followup [question.](https://mathoverflow.net/questions/47035/poincare-conjecture-and-the-graph-of-triangulations) 



The flip graph of triangulations
Just to add a little to Joseph's nice answer, for part 1 of your question: although the problem of computing the flip distance in polynomial time is wide open for triangulations of convex polygons, it can be solved in polynomial time for triangulations of certain highly nonconvex point sets (such as the intersection of the integer lattice with a convex set): see my paper "Happy Endings for Flip Graphs", SoCG 2007 and [JoCG 2010](https://doi.org/10.20382/jocg.v1i1a2).


