DIMACS Discrete Mathematics Seminar
Title:
Computing bounds on degrees of freedom of "molecular frames"
Speaker:
- Deborah Franzblau
- DIMACS
Place:
- CoRE Building, Room 431
- Busch Campus, Rutgers University
Time:
- 4:30 PM
- Tuesday, October 10, 1995
Abstract:
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