EPSRC Reference: 
EP/W019698/1 
Title: 
The graph rigidity problem in arbitrary dimension 
Principal Investigator: 
Nixon, Dr A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics and Statistics 
Organisation: 
Lancaster University 
Scheme: 
Standard Research  NR1 
Starts: 
01 May 2022 
Ends: 
30 April 2023 
Value (£): 
45,952

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Logic & Combinatorics 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Graph rigidity is an interdisciplinary field which aims to provide techniques for identifying rigidity and flexibility properties of discrete geometric structures. The structures may be thought of as assemblies of rigid building blocks with connecting joints and are generally categorised by the nature of these blocks and joints; e.g. barandjoint, bodyandbar and panel andhinge frameworks. Constraint systems of these forms are ubiquitous in nature (e.g. periodic structures in proteins, symmetry in virus capsids and the analysis of materials), in engineering (e.g. tensegrities, trusses, linkages and deployable structures) and in technology (e.g. formation control for multiagent systems, sensor network localisation, machine learning and CAD).
As a simple example, consider a triangle and a square. A triangle is rigid: its angles are determined by the lengths of its edges. A square is flexible: you can deform it into a diamondshape without changing the lengths of its edges. In general, given a structure and a constraint system modelled on the underling graph of the structure, the defining questions of the area are whether: the structure is unique (global rigidity); there are a finite number of realisations satisfying the given constraints (rigidity); or there are infinitely many realisations (flexibility).
Graph rigidity may be traced back to the 18th century and the conjectures of Cauchy and Euler that triangulated structures, such as geodesic domes, which have rigid bars connected together at their endpoints by universal joints, are inherently rigid. While Cauchy obtained a proof in the convex case, subsequent work extending his theorem continued until Connelly demonstrated the existence of flexible polyhedra in the 1970s.
The combinatorial focus of graph rigidity can be traced to James Clerk Maxwell who, in 1864, developed necessary counting conditions on the underlying graph for barjoint structures to be rigid. In general determining when a structure is rigid is NPhard, i.e. it belongs to a family of problems for which it is widely believed there is no efficient solution. However, generically (in the sense of algebraic geometry), rigidity and global rigidity can be expressed as linear algebraic properties (on a Jacobean matrix and a weighted Laplacian matrix respectively), and then attacked by interweaving the theory of matroids and sparse graphs with geometric techniques. Matroids were introduced as a mathematical structure by Whitney in the 1930s. They extend the notion of linear independence of a set of vectors and have numerous important applications in Operational Research and Combinatorial Optimisation.
In 1920 PolaczekGeiringer proved that Maxwell's conditions are sufficient to characterise 2dimensional generic rigidity and crucially this leads quickly to fast deterministic graph orientation algorithms for rigidity testing. However in higher dimensions Maxwell's conditions do not suffice and the ddimensional graph rigidity problem (finding such a characterisation and showing a resulting fast algorithm) remains a crucial open problem of wide potential applicability.
The main aim of the project is to deploy a novel approach in order to resolve the graph rigidity problem. The project will extend foundational results in matroid theory and utilise intricate sparse graph techniques. These tools will then be exploited alongside a very recent strengthening of a classical dimension hopping principle from projective geometry. The techniques should result in groundbreaking combinatorial descriptions of when a generic barjoint structure is rigid or flexible. It will then be of fundamental importance, in a future large project, to investigate the extent to which the descriptions can be tested by fast deterministic algorithms. Given the wide ranging applications, it will also be crucial to implement the algorithms alongside existing software packages such as ProFlex and KINARI.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.lancs.ac.uk 