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

DOI10.1016/J.JSC.2016.02.006MaRDI QIDQ507133zbMATH OpenOpenAlexFDO

Authors Marta R. Hidalgo, Robert Joan-Arinyo

Publication date 3 February 2017

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2117/102162

zbMATH Keywords

geometric constraint graphsgeometric constraint solvingHenneberg sequencesLaman graphsminimally rigid graphstree-decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Towards an optimal algorithm for recognizing Laman graphs
• Certifying and constructing minimally rigid graphs in the plane
• Efficient algorithms for the d-dimensional rigidity matroid of sparse graphs
• On characterizations of rigid graphs in the plane using spanning trees
• Augmenting the rigidity of a graph in \(\mathbb R^{2}\)

Cites work

• DECOMPOSITION OF GEOMETRIC CONSTRAINT SYSTEMS: A SURVEY
• Decomposition plans for geometric constraint problems. II: New algorithms
• Decomposition plans for geometric constraint systems. I: Performance measures for CAD
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 1182943 (Why is no real title available?)
• scientific article; zbMATH DE number 108434 (Why is no real title available?)
• scientific article; zbMATH DE number 3478389 (Why is no real title available?)
• scientific article; zbMATH DE number 482343 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• Planar minimally rigid graphs and pseudo-triangulations
• Rigidity, global rigidity, and graph decomposition
• The non-solvability by radicals of generic 3-connected planar Laman graphs
• The number of embeddings of minimally rigid graphs

Cited in

(2)

• Specified-time bearing-based formation control of multi-agent systems via a dynamic gain approach
• Towards an optimal algorithm for recognizing Laman graphs

This page was built for publication: A Henneberg-based algorithm for generating tree-decomposable minimally rigid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507133)