Efficient algorithms for the d-dimensional rigidity matroid of sparse graphs

Let Rd(G) be the d-dimensional rigidity matroid for a graph G=(V,E). Combinatorial characterization of generically rigid graphs is known only for the plane d=2 [W. Whiteley, Rigidity and scene analysis, in: J.E. Goodman, J. O'Rourke (Eds.), Handbook of Discrete and Computational Geometry, CRC Press LLC, Boca Raton, FL, 2004, pp. 1327–1354, Chapter 60]. Recently Jackson and Jordán [B. Jackson, T. Jordán, The d-dimensional rigidity matroid of sparse graphs, Journal of Computational Theory (B) 95 (2005) 118–133] derived a min-max formula which determines the rank function in Rd(G) when G is sparse, i.e. has maximum degree at most d+2 and minimum degree at most d+1.We present efficient algorithms for sparse graphs G in higher dimensions d⩾3 that(i)detect if E is independent in the rigidity matroid for G, and(ii)construct G using vertex insertions preserving if G is isostatic, and(iii)compute the rank of Rd(G).The algorithms have linear running time assuming that the dimension d⩾3 is fixed.