Nucleation-Free 3D Rigidity

When all non-edge distances of a graph realized in Rd as a bar-and-joint framework are generically implied by the bar (edge) lengths, the graph is said to be rigid in Rd. For d = 3, characterizing rigid graphs, determining implied non-edges and dependent edge sets remains an elusive, long-standing open problem.One obstacle is to determine when implied non-edges can exist without non-trivial rigid induced subgraphs, i.e., nucleations, and how to deal with them.In this paper, we give general inductive construction schemes and proof techniques to generate nucleation-free graphs (i.e., graphs without any nucleation) with implied non-edges. As a consequence, we obtain (a) dependent graphs in 3D that have no nucleation; and (b) 3D nucleation-free rigidity circuits, i.e., minimally dependent edge sets in d = 3. It additionally follows that true rigidity is strictly stronger than a tractable approximation to rigidity given by Sitharam and Zhou [16], based on an inductive combinatorial characterization.As an independently interesting byproduct, we obtain a new inductive construction for independent graphs in 3D. Currently, very few such inductive constructions are known, in contrast to 2D.