The problem of characterizing the 3-dimensional generic rigidity of graphs is one of the major open problems in graph rigidity. Walter Whiteley conjectured that the 3-dimensional generic rigidity matroid coincides with a matroid studied in the context of bivariate splines. With Katie Clinch and Bill Jackson, I gave a solution to the characterization problem for the spline matroid. I will describe our characterization from the viewpoint of constructing maximal matroids on complete graphs. A part of our technique can be extended to a general setting of matroids. I will show that Graver's unique maximality conjecture for abstract rigidity matroids is related to the combinatorial characterization problem for various variants of graph rigidity.

The talk is based on joint work with Bill Jackson.