# Graph Rigidity and Molecular Conformation

Graph rigidity is a somewhat obscure topic that turns out to have
a surprising number of applications in the physical sciences.
Imagine placing all the vertices of a graph at random points in
space. Can you now move the vertices without changing the lengths
of any of the graph's edges? (Trivial motions don't count.) If
not, the graph is * rigid*, otherwise it is * flexible*.
Not surprisingly the answer depends on the dimensionality of the
space in which you place the vertices. In my thesis work, I
established a connection between graph rigidity and the
determination of protein conformation from NMR data. The graph
algorithms and properties I developed are described in the first
paper below, while the application to molecular conformation is
discussed in the second. More recently, Don Jacobs and Mike Thorpe,
physicists at Michigan State, have recognized a connection with
a discipline known as * rigidity percolation*. I have
worked with them to adapt and implement my algorithms towards
this end as discussed in the third paper.

## Papers

Return to Bruce's home page