certifying and constructing minimally rigid graphs in the plane
We study minimally rigid graphs in the plane or plane isostatic graphs. These graphs (also called Laman graphs ) admit characterizations based on decomposition into trees (Crapo's theorem and Rcski's theorem). Tree partitions can be viewed as certificates of plane isostatic graphs. Unfortunately, they require ?(n 2 ) time to verify their validity where n is the number of vertices in the graph. We present a new construction (which can be viewed as a hierarchical decomposition of the graph) called red-black hierarchy that (i) is a certificate for plane isostatic graphs, and (ii) can be verified in linear time. We also show that it can be computed in O(n 2 ) time.A classical result in Rigidity Theory by Henneberg [9] states that the plane isostatic graphs can be constructed incrementally by special vertex insertions. We study the following computational problem: given a Laman graph G, compute a sequence of Henneberg insertions that yields G. We show that the red-bl ack hierarchy can be used to compute a Henneberg construction in O(n 2 ) time. Applied to planar graphs our algorithm can speed up a recent algorithm by Haas et al. [8] for embedding a planar Laman graph as a pointed pseudo-triangulation by a factor of O(n).
rigidity theory henneberg construction pseudo-triangulation computational geometry tree decomposition