Generic rigidity of molecular graphs via ear decomposition (Q1975368)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generic rigidity of molecular graphs via ear decomposition |
scientific article |
Statements
Generic rigidity of molecular graphs via ear decomposition (English)
0 references
16 July 2000
0 references
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.
0 references
graph rigidity
0 references
generic rigidity
0 references
degrees of freedom
0 references
frame
0 references
framework
0 references
molecular graph
0 references
ear decomposition
0 references