Universal Rigidity of Complete Bipartite Graphs

详细信息    查看全文

• 作者：Robert Connelly ; Steven J. Gortler
• 关键词：Rigidity ; Prestress stability ; Universal rigidity
• 刊名：Discrete & Computational Geometry
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：57
• 期：2
• 页码：281-304
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1432-0444
• 卷排序：57

文摘

We describe a very simple condition that is necessary for the universal rigidity of a complete bipartite framework \((K(n,m),\mathbf{p},\mathbf{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.