Equivalent realisations of a rigid graph

DOI10.1016/J.DAM.2017.12.009MaRDI QIDQ1728093zbMATH OpenOpenAlexFDO

Authors Bill Jackson, J. C. Owen

Publication date 21 February 2019

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

Full work available at URL https://arxiv.org/abs/1204.1228, http://qmro.qmul.ac.uk/xmlui/handle/123456789/31438

zbMATH Keywords

rigid frameworknumber of equivalent realisations

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: Given a rigid realisation of a graph $G$ in ${mathbbR}^2$, it is an open problem to determine the maximum number of pairwise non-congruent realisations which have the same edge lengths as the given realisation. This problem can be restated as finding the number of solutions of a related system of quadratic equations and in this context it is natural to consider the number of solutions in ${mathbbC}^2$ rather that ${mathbbR}^2$. We show that the number of complex solutions, $c(G)$, is the same for all generic realisations of a rigid graph $G$, characterise the graphs $G$ for which $c(G)=1$, and show that the problem of determining $c(G)$ can be reduced to the case when $G$ is $3$-connected and has no non-trivial $3$-edge-cuts. We consider the effect of the Henneberg moves and the vertex-splitting operation on $c(G)$. We use our results to determine $c(G)$ exactly for two important families of graphs, and show that the graphs in both families have $c(G)$ pairwise equivalent generic real realisations. We also show that every planar isostatic graph on $n$ vertices has at least $2^{n-3}$ pairwise equivalent real realisations.

Recommendations

• Lower bounds on the number of realizations of rigid graphs
• On the number of embeddings of minimally rigid graphs
• The number of realizations of a Laman graph
• Connected rigidity matroids and unique realizations of graphs
• Counting realizations of Laman graphs on the sphere

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4194602 (Why is no real title available?)
• scientific article; zbMATH DE number 1955467 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3075369 (Why is no real title available?)
• 1-extensions and global rigidity of generic direction-length frameworks
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• Algorithms for graph rigidity and scene analysis
• Algorithms – ESA 2004
• Characterizing generic global rigidity
• Computing the number of realizations of a Laman graph
• Conditions for Unique Graph Realizations
• Connected rigidity matroids and unique realizations of graphs
• Counting the Number of Solutions of KDMDGP Instances
• Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
• Generic global rigidity
• Globally linked pairs of vertices in equivalent realizations of graphs
• LamanGraphs
• Mixed volume and distance geometry techniques for counting Euclidean embeddings of rigid graphs
• Mixed volume techniques for embeddings of Laman graphs
• On Generic Rigidity in the Plane
• On graphs and rigidity of plane skeletal structures
• On the number of realizations of certain Henneberg graphs arising in protein conformation
• Randomized embeddings with slack and high-dimensional approximate nearest neighbor
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• The discretizable molecular distance geometry problem seems easier on proteins
• The non-solvability by radicals of generic 3-connected planar Laman graphs
• The number of embeddings of minimally rigid graphs
• The rigidity of graphs. II

Cited in

(14)

• Coupler curves of moving graphs and counting realizations of rigid graphs
• The m-Bézout bound and distance geometry
• Realizations of rigid graphs
• On the multihomogeneous Bézout bound on the number of embeddings of minimally rigid graphs
• The number of realizations of a Laman graph
• Lower bounds on the number of realizations of rigid graphs
• One brick at a time: a survey of inductive constructions in rigidity theory
• The number of realisations of a rigid graph in Euclidean and spherical geometries
• On the maximal number of real embeddings of minimally rigid graphs in \(\mathbb{R}^2,\mathbb{R}^3\) and \(S^2\)
• Generic Global Rigidity in Complex and Pseudo-Euclidean Spaces
• scientific article; zbMATH DE number 6470135 (Why is no real title available?)
• New upper bounds for the number of embeddings of minimally rigid graphs
• Connected rigidity matroids and unique realizations of graphs
• Counting realizations of Laman graphs on the sphere

Describes a project that uses

Uses Software

• LamanGraphs

This page was built for publication: Equivalent realisations of a rigid graph

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