Realizability of Graphs and Linkages

We show that deciding whether a graph with given edge lengths can be realized by a straight-line drawing has the same complexity as deciding the truth of sentences in the existential theory of the real numbers, ETR; we introduce the class $$\exists \mathbb{R}$$ that captures the computational complexity of ETR and many other problems. The graph realizability problem remains $$\exists \mathbb{R}$$ -complete if all edges have unit length, which implies that recognizing unit distance graphs is $$\exists \mathbb{R}$$ -complete. We also consider the problem for linkages: In a realization of a linkage, vertices are allowed to overlap and lie on the interior of edges. Linkage realizability is $$\exists \mathbb{R}$$ -complete and remains so if all edges have unit length. A linkage is called rigid if any slight perturbation of its vertices that does not break the linkage (i.e., keeps edge lengths the same) is the result of a rigid motion of the plane. Testing whether a configuration is not rigid is $$\exists \mathbb{R}$$ -complete.