Directed graphs, decompositions, and spatial linkages
The decomposition of a linkage into minimal components is a central tool of analysis and synthesis of linkages. In this paper we prove that every pinned d d -isostatic (minimally rigid) graph (grounded linkage) has a unique decomposition into minimal strongly connected components (in the sense of directed graphs), or equivalently into minimal pinned isostatic graphs, which we call d d -Assur graphs. We also study key properties of motions induced by removing an edge in a d d -Assur graph  defining a sharper subclass of strongly d d -Assur graphs by the property that all inner vertices go into motion, for each removed edge. The strongly 3-Assur graphs are the central building blocks for kinematic linkages in 3-space and the 3-Assur graphs are components in the analysis of built linkages. The d d -Assur graphs share a number of key combinatorial and geometric properties with the 2-Assur graphs, including an associated lower block-triangular decomposition of the pinned rigidity matrix which provides modular information for extending the motion induced by inserting one driver in a bottom Assur linkage to the joints of the entire linkage. We also highlight some problems in combinatorial rigidity in higher dimensions (d?3 d ? 3 ) which cause the distinction between d d -Assur and strongly d d -Assur which did not occur in the plane.
directed graph decomposition isostatic framework assur graphs algorithms