Global rigidity of direction-length frameworks

DOI10.1016/J.JCTB.2020.05.003zbMATH Open1451.52012arXiv1607.00508OpenAlexW3030839719MaRDI QIDQ2200920FDOQ2200920

Authors: Katie Clinch, Bill Jackson, Peter Keevash 

Publication date: 24 September 2020

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A 2-dimensional direction-length framework is a collection of points in the plane which are linked by pairwise constraints that fix the direction or length of the line segments joining certain pairs of points. We represent it as a pair $(G,p)$, where $G=(V;D,L)$ is a `mixed' graph and $p:Vo{mathbbR}^2$ is a point configuration for $V$. It is globally rigid if every direction-length framework $(G,q)$ which satisfies the same constraints can be obtained from $(G,p)$ by a translation or a rotation by $180^{c}irc$. We show that the problem of characterising when a generic framework $(G,p)$ is globally rigid can be reduced to the case when $G$ belongs to a special family of `direction irreducible' mixed graphs, and prove that {every} generic realisation of a direction irreducible mixed graph $G$ is globally rigid if and only if $G$ is 2-connected, direction-balanced and redundantly rigid.

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

Recommendations

• Globally rigid circuits of the direction-length rigidity matroid
• Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
• Necessary conditions for the global rigidity of direction-length frameworks
• Bounded direction-length frameworks
• Operations preserving global rigidity of generic direction-length frameworks

zbMATH Keywords

global rigiditydirection-length frameworks

Mathematics Subject Classification ID

Graph theory (05C99) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Cites Work

• Title not available (Why is that?)
• Connected rigidity matroids and unique realizations of graphs
• Pebble game algorithms and sparse graphs
• On graphs and rigidity of plane skeletal structures
• Title not available (Why is that?)
• Decomposition of Finite Graphs Into Forests
• Algorithms for graph rigidity and scene analysis
• Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
• The Union of Matroids and the Rigidity of Frameworks
• Dividing a Graph into Triconnected Components
• Constraining Plane Configurations in Computer-Aided Design: Combinatorics of Directions and Lengths
• 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
• Algorithms for Graphic Polymatroids and Parametrics-Sets

Cited In (15)

• Globally linked pairs of vertices in equivalent realizations of graphs
• 1-extensions and global rigidity of generic direction-length frameworks
• Polygons with prescribed angles in 2D and 3D
• Bounded direction-length frameworks
• Necessary conditions for the global rigidity of direction-length frameworks
• Global rigidity of two-dimensional framework
• On affine motions and universal rigidity of tensegrity frameworks
• Operations preserving global rigidity of generic direction-length frameworks
• Polygons with Prescribed Angles in 2D and 3D
• Graph reconstruction from unlabeled edge lengths
• Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
• Globally linked pairs of vertices in rigid frameworks
• Double-distance frameworks and mixed sparsity graphs
• Assur decompositions of direction-length frameworks
• Global rigidity of triangulations with braces

This page was built for publication: Global rigidity of direction-length frameworks

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