Efficient algorithms for the \(d\)-dimensional rigidity matroid of sparse graphs (Q2479473)

Let \(G\) be a graph with maximum degree at most \(d + 2\) and minimum degree at most \(d + 1\), and consider the \(d\)-dimensional generic rigidity matroid of \(G\). By a recent result of \textit{B. Jackson} and \textit{T. Jordán} in [J. Comb. Theory, Ser. B 95, No. 1, 118--133 (2005; Zbl 1070.05022)] the dependent sets of the generic \(d\)-dimensional rigidity matroid of such sparse graphs are exactly those that violate Laman's condition, and are therefore of limited size, bounded by \(\frac{(d - 1)(d+2)}{(d -2)}\) for \(d \geq 3\). This fact is used to obtain an algorithm, linear in \(n\), to detect independence of the edge set of \(G\). Moreover, if \(G\) is generically isostatic an algorithm is given, also linear in \(n\), to construct a Henneberg sequence for \(G\).