Faster Algorithms for Rigidity in the Plane

Details Faster Algorithms for Rigidity in the Plane Faster Algorithms for Rigidity in the Plane

2007-11-19

arxiv.org/abs/0711.2835v2

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Faster Algorithms for Rigidity in the Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Faster Algorithms for Rigidity in the Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Faster Algorithms for Rigidity in the Plane will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115497