Gábor Damásdi


Characterizing diameter graphs in R^3 using rigidity theory.

Vázsonyi conjectured that any set of n points in R^3 determines at most 2n-2 diameter pairs. The conjecture was proven independently by Grünbaum, Heppes and Straszewicz using ball polyhedra. Later Swanepoel and Pinchasi gave new proofs using different methods. They showed that any diameter graph can be drawn in the projective plane such that any region has a boundary of even length. Monetjano, Pauli, Raggi, and Roldan-Pensado conjectured that the converse also holds, that is, for any such graph G that there is a point set in R^3 whose diameter graph is isomorphic to G.  Whe show that this is indeed true, completing the characterization of diameter graphs in R^3. This result also implies new constructions of Reuleaux polyhedra, ball-polyhedra, Meissner bodies  and bodies of constant width. The proof uses ideas from rigidity theory.