Carregant...
Carregant...

Vés al contingut (premeu Retorn)

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

Autor
Hidalgo, M.; Joan-Arinyo, R.
Tipus d'activitat
Article en revista
Revista
Journal of symbolic computation
Data de publicació
2017-03-01
Volum
79, Part 2
Pàgina inicial
232
Pàgina final
248
DOI
https://doi.org/10.1016/j.jsc.2016.02.006 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/102162 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0747717116000158 Obrir en finestra nova
Resum
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...
Citació
Hidalgo, M., Joan-Arinyo, R. A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs. "Journal of symbolic computation", 1 Març 2017, vol. 79, Part 2, p. 232-248.
Paraules clau
Geometric constraint graphs, Geometric constraint solving, Henneberg sequences, Laman graphs, Minimally rigid graphs, Tree-decomposition
Grup de recerca
CREB - Centre de Recerca en Enginyeria Biomedica
GIE - Grup d'Informàtica a l'Enginyeria

Participants