A polygon $P_k$ divided by $k-2$ diaginals 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.