Generic rigidity of molecular graphs via ear decomposition

DOI10.1016/S0166-218X(99)00188-2MaRDI QIDQ1975368zbMATH OpenOpenAlexFDO

Authors D. S. Franzblau

Publication date 16 July 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00188-2

zbMATH Keywords

degrees of freedomear decompositionframeframeworkgeneric rigiditygraph rigiditymolecular graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Rigid components in molecular graphs
• Combinatorial Algorithm for a Lower Bound on Frame Rigidity
• On the rigidity of molecular graphs
• Lower bounds on the number of realizations of rigid graphs
• The forcing polynomial of catacondensed hexagonal systems
• The number of embeddings of minimally rigid graphs
• scientific article; zbMATH DE number 5627530
• Cut-edges and the independence number
• On polyhedron graph density in problems of combinatorial optimization
• Isostatic block and hole frameworks

Cites work

• Combinatorial Algorithm for a Lower Bound on Frame Rigidity
• Conditions for Unique Graph Realizations
• Ear decomposition with bounds on ear length
• HANS BETHE'S CONTRIBUTIONS TO SOLID-STATE PHYSICS
• scientific article; zbMATH DE number 3889718 (Why is no real title available?)
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 3953697 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• Infinitesimally Rigid Polyhedra. I. Statics of Frameworks
• On graphs and rigidity of plane skeletal structures
• The Algebraic Geometry of Stresses in Frameworks
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(2)

• On the rigidity of molecular graphs
• ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID

This page was built for publication: Generic rigidity of molecular graphs via ear decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1975368)