Faster Algorithms for Rigidity in the Plane
| dc.creator | Bereg, Sergey | |
| dc.date | 2007-11-19 | |
| dc.date | 2008-02-29 | |
| dc.date.accessioned | 2026-07-07T09:23:41Z | |
| dc.date.available | 2026-07-07T09:23:41Z | |
| dc.description | In [1], a new construction called red-black hierarchy characterizing Laman graphs and an algorithm for computing it were presented. For a Laman graph G=(V,E) with n vertices it runs in O(n^2) time assuming that a partition of (V,E+e) into two spanning trees is given. We show that a simple modification reduces the running time to O(n\log n). The total running time can be reduced O(n\sqrt{n\log n}) using the algorithm by Gabow and Westermann [2] for partitioning a graph into two forests. The existence of a red-black hierarchy is a necessary and sufficient condition for a graph to be a Laman graph. The algorithm for constructing a red-black hierarchy can be then modified to recognize Laman graphs in the same time. | |
| dc.identifier | https://arxiv.org/abs/0711.2835 | |
| dc.identifier | http://arxiv.org/abs/0711.2835 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/155823 | |
| dc.subject | Computational Geometry | |
| dc.title | Faster Algorithms for Rigidity in the Plane | |
| dc.type | text |