**Reference**:- Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl, “Who Needs Crossings? Hardness of Plane Graph Rigidity”, in
*Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016)*, Boston, Massachusetts, June 14–18, 2016, 3:1–3:15. **Abstract**:-
We exactly settle the complexity of graph realization, graph rigidity, and graph global rigidity as applied to three types of graphs: “globally noncrossing” graphs, which avoid crossings in all of their configurations; matchstick graphs, with unit-length edges and where only noncrossing configurations are considered; and unrestricted graphs (crossings allowed) with unit edge lengths (or in the global rigidity case, edge lengths in {1, 2}). We show that all nine of these questions are complete for the class ∃ℝ, defined by the Existential Theory of the Reals, or its complement ∀ℝ; in particular, each problem is (co)NP-hard.
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 nontrivial regions in the plane that may be traced by a noncrossing linkage are precisely the compact semialgebraic regions. Thus, no drawing power is lost by restricting to noncrossing linkages. We prove analogous results for matchstick linkages and unit-distance linkages as well. **Availability**:- The paper is available in PDF (716k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated December 15, 2022 by Erik Demaine.