View article

In this paper we use a single unifying approach (which we call the Principal Lattice of Partitions approach) to construct simple and fast algorithms for problems including and related to the “Principal Partition” and the “Generic Rigidity” of graphs. Most of our algorithms are at least as fast as presently known algorithms for these problems, while our algorithm for Principal Partition problem (complete partition and the partial orders for all critical values) runs in O(¦E∥V¦²log²¦V¦) time and is the fastest known so far.