A semidefinite programming approach to tensegrity theory and realizability of graphs

Recently, Connelly and Sloughter [14] 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 re-alizing those graphs. In this paper, we resolve that question by showing that the semidefinite programming (SDP) approach of [11, 32] can be used for realizing 3– realizable graphs. Specifically, we use SDP duality the-ory 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 re-alization of G. Using this result and the techniques in [14, 31], we then obtain a polynomial time algorithm for (approximately) realizing 3–realizable graphs. Our re-sults also establish a little–explored connection between SDP and tensegrity theories and allow us to derive some interesting properties of tensegrity frameworks. 1