On the atomic decomposition length of graphs and tensegrities

Abstract

In this study, a complexity measure for graphs and tensegrities is proposed, based on the concept of atomic decomposition.We state several results on the relationship between atomic decompositions and spaces of self-stresses for generically rigid graphs, and study the computational complexity of finding atomic decompositions of minimal length.