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

DOI10.1016/J.DAM.2022.10.017MaRDI QIDQ2104943zbMATH OpenOpenAlexFDO

Authors Katie Clinch

Publication date 8 December 2022

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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)

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.

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

Cites work

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

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
• Graded sparse graphs and body-length-direction frameworks
• Operations preserving global rigidity of generic direction-length 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)