Directed graphs, decompositions, and spatial linkages

DOI10.1016/J.DAM.2013.06.004MaRDI QIDQ2446895zbMATH OpenOpenAlexFDO

Authors Adnan Sljoka, Offer Shai, Walter Whiteley

Publication date 23 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5552

zbMATH Keywords

assur graphsdecompositiondirected graphisostatic framework

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: 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-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-Assur graphs. We also study key properties of motions induced by removing an edge in a d-Assur graph - defining a stronger sub-class of strongly 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-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 > 2) which cause the distinction between d-Assur and strongly d-Assur which did not occur in the plane.

Recommendations

• Assur decompositions of direction-length frameworks
• Combinatorial characterization of the Assur graphs from engineering
• Geometric properties of Assur graphs
• Symmetry adapted assur decompositions
• Generating all rigidity circuits on at most 10 vertices and all Assur graphs on at most 11 vertices

Cites work

• Chebychev-Grübler-Kutzbach's criterion for mobility calculation of multi-loop mechanisms revisited via theory of linear transformations
• Combinatorial characterization of the Assur graphs from engineering
• CONSTRAINTS ON SIMPLE GEOMETRY IN TWO AND THREE DIMENSIONS
• Decomposition plans for geometric constraint problems. II: New algorithms
• Decomposition plans for geometric constraint systems. I: Performance measures for CAD
• Depth-First Search and Linear Graph Algorithms
• Geometric properties of Assur graphs
• scientific article; zbMATH DE number 3846996 (Why is no real title available?)
• scientific article; zbMATH DE number 3868113 (Why is no real title available?)
• scientific article; zbMATH DE number 3917126 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• ON GENERAL PHYSICAL SYSTEMS THEORIES
• Pebble game algorithms and sparse graphs
• Position analysis in polynomial form of planar mechanisms with Assur groups of class 3 including revolute and prismatic joints.
• Relative centers of motion, implicit bars and dead-center positions for planar mechanisms
• Rooted-tree decompositions with matroid constraints and the infinitesimal rigidity of frameworks with boundaries
• The Algebraic Geometry of Motions of Bar-and-Body Frameworks
• The Rigidity of Graphs

Cited in

(9)

• Isostatic bar and joint frameworks in the plane with irreducible pure conditions
• Structural properties of the line-graphs associated to directed networks
• Assur decompositions of direction-length frameworks
• New upper bounds for the number of embeddings of minimally rigid graphs
• Symmetry adapted assur decompositions
• Topological Decomposition of Directed Graphs
• Generating all rigidity circuits on at most 10 vertices and all Assur graphs on at most 11 vertices
• Combinatorial characterization of the Assur graphs from engineering
• Geometric properties of Assur graphs

This page was built for publication: Directed graphs, decompositions, and spatial linkages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446895)