Certifying and constructing minimally rigid graphs in the plane

DOI10.1145/1064092.1064106zbMath1387.68238OpenAlexW2066603407MaRDI QIDQ5370598

Sergey Bereg

Publication date: 20 October 2017

Published in: Proceedings of the twenty-first annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1064092.1064106

zbMATH Keywords

tree decompositioncomputational geometryrigidity theoryHenneberg constructionpseudo-triangulation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The Number of Realizations of a Laman Graph, Stabilisation of infinitesimally rigid formations of multi-robot networks, Enumerating Grid Layouts of Graphs, Certifying algorithms, Pebble game algorithms and sparse graphs, Switching formation shape control with distance + area/angle feedback, Further results on the distance and area control of planar formations