Generic rigidity of molecular graphs via ear decomposition (Q1975368)

The paper considers the problem of computing the generic degrees of freedom of a graph in a three-dimensional space, denoted by \(\psi(G)\), using combinatorial methods. The degrees of freedom of a realization of a graph (a mapping sending each vertex to a point in a three-dimensional Euclidean space) is the dimension of the space of infinitesimal moves of its vertices. This measure becomes generic if it depends only on the graph itself. The main results of the paper give various recurrences to compute lower and upper bounds for \(\psi(G)\). Each recurrence is obtained from a set of decomposition lemmas, proved using basic linear algebra applied to the rigidity matrix of the graph. As a corollary, one obtains an algorithm to effectively compute the lower and upper bounds. The paper improves previous results of the author for the computation of a lower bound for \(\psi(G)\); compare \textit{D. S. Franzblau} [Combinatorial algorithm for a lower bound on frame rigidity, SIAM J. Discrete Math. 8, No. 3, 388-400 (1995; Zbl 0829.73076)]. The exact value for \(\psi(G)\) can be computed for two particular classes of graphs. Special attention is given to molecular graphs.