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 was told a few years ago that some complexity problem for the triangulation graph (perhaps in dimension 3?) is related to the Poincar'e conjecture. Unfortunately I forgot what was the problem. Does anybody know?