Universal Rigidity of Complete Bipartite Graphs

Abstract

We describe a very simple condition that is necessary for the universal rigidity of a complete bipartite framework $(K(n,m),p,q)$. This condition is also sufficient for universal rigidity under a variety of weak assumptions, such as general position. Even without any of these assumptions, in complete generality, we extend these ideas to obtain an efficient algorithm, based on a sequence of linear programs, that determines whether an input framework of a complete bipartite graph is universally rigid or not.

DCG published version

References in corpus (1)

• Matrices with high completely positive semidefinite rank

Cited by in corpus (3)

• Matrices with high completely positive semidefinite rank
• Singularity Degree of the Positive Semidefinite Matrix Completion Problem
• The Signed Positive Semidefinite Matrix Completion Problem for Odd-$K_4$ Minor Free Signed Graphs