A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs

详细信息    查看全文

• 作者：Marta R. Hidalgo^a ; ^{mhidalgo@cipf.es" class="auth_mail" title="E-mail the corresponding author} ; Robert Joan-Arinyo^b ; ^{robert@cs.upc.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Minimally rigid graphs ; Laman graphs ; Henneberg sequences ; Geometric constraint solving ; Geometric constraint graphs ; Tree-decomposition
• 刊名：Journal of Symbolic Computation
• 出版年：2017
• 出版时间：March-April 2017
• 年：2017
• 卷：79
• 期：part_P2
• 页码：232-248
• 全文大小：670 K

文摘

In this work we describe an algorithm to generate tree-decomposable minimally rigid graphs on a given set of vertices V  . The main idea is based on the well-known fact that all minimally rigid graphs, also known as Laman graphs, can be generated via Henneberg sequences. Given that not each minimally rigid graph is tree-decomposable, we identify a set of conditions on the way Henneberg steps are applied so that the resulting graph is tree-decomposable. We show that the worst case running time of the algorithm is O(|V|³)$O(|V{|}^3)$.