One of these nine results—that realization of unit-distance graphs is ∃ℝ-complete—was shown previously by Schaefer (2013), but the other eight are new. We strengthen several prior results. Matchstick graph realization was known to be NP-hard (Eades & Wormald 1990, or Cabello et al. 2007), but its membership in NP remained open; we show it is complete for the (possibly) larger class ∃ℝ. Global rigidity of graphs with edge lengths in {1, 2} was known to be coNP-hard (Saxe 1979); we show it is ∀ℝ-complete.
The majority of the paper is devoted to proving an analog of Kempe's Universality Theorem—informally, “there is a linkage to sign your name”—for globally noncrossing linkages. In particular, we show that any polynomial curve φ(x, y) = 0 can be traced by a noncrossing linkage, settling an open problem from 2004. More generally, we show that the regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions (plus the trivial case of the entire plane). Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well.