A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs. (March 2017) - Hidalgo, Marta R.; Joan-Arinyo, Robert
Abstract: 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 | 3 ) .