Experiments on Universal Rigidity of Bipartite Graphs

Abstract

Our goal is to characterize necessary and sufficient conditions for the universal rigidity of bipartite frameworks. Previous work describe ways to test universal rigidity through semidefinite program- ming using stress matrix as a tool. Also, it had been shown a relationship between rigidity of a bipartite framework and quadric separability of the two sets of vertices. In particular, previous work showed that given a complete bipartite framework, separability by a quadric implied non- rigidity of the framework. Based on this, a reasonable conjecture was that the reciprocal could also be true. Our goal was to develop experiments using semidefinite programming to validate this conjecture for complete bipartite framework, and observe the behavior of rigidity for incomplete bipartite frameworks.