Generic rigidity of molecular graphs via ear decomposition
type: Item
instance of: scholarly article
title: Generic rigidity of molecular graphs via ear decomposition
zbMATH Open document ID: 0940.05063
DOI: 10.1016/S0166-218X(99)00188-2
author: D. S. Franzblau
published in: Discrete Applied Mathematics
publication date: 2000-07-16T00:00:00Z
review text: 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.
reviewed by: G. Melançon
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1428620
zbMATH Keywords: graph rigidity
zbMATH Keywords: generic rigidity
zbMATH Keywords: degrees of freedom
zbMATH Keywords: frame
zbMATH Keywords: framework
zbMATH Keywords: molecular graph
zbMATH Keywords: ear decomposition
MaRDI profile type: Publication
cites work: HANS BETHE'S CONTRIBUTIONS TO SOLID-STATE PHYSICS
cites work: Q3723208
cites work: Combinatorial Algorithm for a Lower Bound on Frame Rigidity
cites work: Ear decomposition with bounds on ear length
cites work: Q4279195
cites work: Conditions for Unique Graph Realizations
cites work: On graphs and rigidity of plane skeletal structures
cites work: Q3222981
cites work: Q3694165
cites work: Infinitesimally Rigid Polyhedra. I. Statics of Frameworks
cites work: The Union of Matroids and the Rigidity of Frameworks
cites work: The Algebraic Geometry of Stresses in Frameworks
full work available at URL: s0166-218x(99)00188-2
OpenAlex ID: W2073188722
Recommended article: Rigid components in molecular graphs
Recommended article: Combinatorial Algorithm for a Lower Bound on Frame Rigidity
Recommended article: On the rigidity of molecular graphs
Recommended article: Lower Bounds on the Number of Realizations of Rigid Graphs
Recommended article: Q5279119
Recommended article: The number of embeddings of minimally rigid graphs
Recommended article: Q3643746
Recommended article: Q5310097
Recommended article: On polyhedron graph density in problems of combinatorial optimization
Recommended article: Isostatic block and hole frameworks
description: scientific article; zbMATH DE number 1428620