Return to Question

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.

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.

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.

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.

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?

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.