DIMACS Discrete Mathematics Seminar


Computing bounds on degrees of freedom of "molecular frames"


Deborah Franzblau


CoRE Building, Room 431
Busch Campus, Rutgers University


4:30 PM
Tuesday, October 10, 1995


A central open problem in the theory of structural rigidity is to find a combinatorial algorithm to compute the number of degrees of freedom of a frame in 3 dimensions. A frame is a graph that is realized in Euclidean space with straight-line edges; each edge represents a constraint that fixes the distance between its endpoints. The number of degrees of freedom is the dimension of the configuration space of the vertices, given the edge constraints. In materials physics, the computation of degrees of freedom is an important tool for understanding the properties of atom-bond graph models of materials; in that case the angles between neighboring edges, as well as the lengths of the edges, are fixed. A molecular frame is a frame with these additional angle constraints. In earlier work I showed that one can compute a lower bound on the degrees of freedom of molecular frames using a chain decomposition (similar to an ear decomposition) of the underlying graph. In this talk I will discuss new results which show that chain decomposition can also be used to compute an upper bound. I will show how these results lead to polynomial-time algorithms to compute the degrees of freedom for the class of molecular frames which have decompositions into either "short" or "long" chains.
Document last modified on October 4, 1995