Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids

DOI10.1016/J.DAM.2022.10.017zbMATH Open1504.05070arXiv1608.08559OpenAlexW2514933739MaRDI QIDQ2104943FDOQ2104943

Authors: Katie Clinch 

Publication date: 8 December 2022

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

Abstract: A two-dimensional direction-length framework $(G,p)$ consists of a multigraph $G=(V;D,L)$ whose edge set is formed of "direction" edges $D$ and "length" edges $L$, and a realisation $p$ of this graph in the plane. The edges of the framework represent geometric constraints: length edges fix the distance between their endvertices, whereas direction edges specify the gradient of the line through both endvertices. A direction-length framework $(G,p)$ is globally rigid if every framework $(G,q)$ which satisfies the same direction and length constraints as $(G,p)$ can be obtained by translating $(G,p)$ in the plane, and/or rotating $(G,p)$ by $180^{circ}$. In this paper, we characterise global rigidity for generic direction-length frameworks whose associated rigidity matroid is connected, by showing that such frameworks are globally rigid if and only if every 2-separation of the underlying graph is direction-balanced.

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

Recommendations

• Global rigidity of direction-length frameworks
• Globally rigid circuits of the direction-length rigidity matroid
• Necessary conditions for the global rigidity of direction-length frameworks
• Operations preserving global rigidity of generic direction-length frameworks
• Global rigidity of two-dimensional framework

zbMATH Keywords

global rigidityrigidity matroiddirection-length framework

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Connected rigidity matroids and unique realizations of graphs
• On graphs and rigidity of plane skeletal structures
• Characterizing generic global rigidity
• Title not available (Why is that?)
• The rigidity of graphs. II
• Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Bounded direction-length frameworks
• Necessary conditions for the global rigidity of direction-length frameworks
• Globally rigid circuits of the direction-length rigidity matroid
• Operations preserving global rigidity of generic direction-length frameworks
• Independence and port oracles for matroids, with an application to computational learning theory
• Global rigidity of direction-length frameworks

Cited In (9)

• 1-extensions and global rigidity of generic direction-length frameworks
• A characterisation of the generic rigidity of 2-dimensional point-line frameworks
• Bounded direction-length frameworks
• Necessary conditions for the global rigidity of direction-length frameworks
• On the two-dimensional generic rigidity matroid and its dual
• Globally rigid circuits of the direction-length rigidity matroid
• Operations preserving global rigidity of generic direction-length frameworks
• Graded sparse graphs and body-length-direction frameworks
• Global rigidity of direction-length frameworks

This page was built for publication: Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids

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