Center for Computing Research (CCR)

Center for Computing Research


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.


  • The Molecule Problem: Exploiting Structure in Global Optimization, Bruce Hendrickson. SIAM J. Opt., 5(4):835-857, 1995.


Contact: Collis, Samuel Scott,
SAND2015-2637 S