A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs
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...
| Autores: | ; |
|---|---|
| Tipo de documento: | Artículo |
| Estado: | Published version |
| Fecha de publicación: | 2017 |
| País: | España |
| Institución: | Fundación para el Fomento de la Investigación Sanitaria y Biomédica de la Comunitat Valenciana (FISABIO) |
| Repositorio: | r-FISABIO. Repositorio Institucional de Producción Científica |
| OAI Identifier: | oai:fisabio.fundanetsuite.com:p13038 |
| Acceso en línea: | https://fisabio.portalinvestigacion.com/publicaciones/13038 |
| Nivel de acceso: | Acceso abierto |
| Palabra clave: | Minimally rigid graphs Laman graphs Henneberg sequences Geometric constraint solving Geometric constraint graphs Tree-decomposition |
| Sumario: | 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 (vertical bar V vertical bar(3)). (C) 2016 Elsevier Ltd. All rights reserved. |
|---|