Title: A Semidefinite Programming Approach to Tensegrity Theory 
       and Realizability of Graphs 

Speaker: Man Cho Anthony So
Stanford University

Date: Friday, Sept 16, 2005
Time 12-1 [Note: SPECIAL TIME]
Venue: Room 3464 , HKUST   


Abstract 
Recently, Connelly and Sloughter have introduced the notion of 
d-realizability of graphs and have, among other things, given a 
complete characterization of the class of 3-realizable graphs.  
However, their work has left open the question of finding an algorithm 
for realizing those graphs.  We resolve that question by showing 
that the semidefinite progamming approach developed by Biswas and Ye 
can be used for realizing 3-realizable graphs.  Specifically, we use 
SDP duality theory to show that given a graph G and a set of 
lengths on its edges, the optimal dual multipliers of a certain SDP 
give rise to a proper equilibrium stress for some realization of G.  
Using this result and the techniques developed by Connelly and Sloughter, 
we then obtain an algorithm for realizing 3-realizable graphs.  
Our results also establish a previously unexplored connection between 
SDP and tensegrity theories and allow us to derive some interesting 
properties of tensegrity frameworks.