Who Needs Crossings?: Noncrossing Linkages are Universal, and Deciding (Global) Rigidity is Hard

Zachary Abel, Erik D. Demaine, Martin L. Demaine +3

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 cro…