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. 

<b> Question 1. </b> Is it in P? 

<b> Question 2. </b> What is known about the complexity of finding the shortest path in the triangulation graph of other surfaces?

<b> Update. </b> 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?