Generic global rigidity in three dimensions
Decide whether a graph is globally rigid in three-dimensional space.
In a paper by Gortler, Healy, and Thurston , it is shown that global rigidity of a generic framework depends only on the graph, so global rigidity of graphs can be defined in any dimension. Furthermore, they show that global rigidity of a graph can be determined by computing the rank of a matrix of indeterminates, thus there is a randomized polynomial algorithm. Jackson, McCourt, and Nixon  give necessary conditions for global rigidity on various surfaces, and propose a conjecture that would imply a polynomial algorithm for generic global rigidity on a cylinder or a cone.