The number of realisations of a rigid graph in Euclidean and spherical geometries

Sean Dewar, Georg Grasegger

Research output: Working paperPreprint

14 Downloads (Pure)

Abstract

A graph is $d$-rigid if for any generic realisation of the graph in $\mathbb{R}^d$ (equivalently, the $d$-dimensional sphere $\mathbb{S}^d$), there are only finitely many non-congruent realisations in the same space with the same edge lengths. By extending this definition to complex realisations in a natural way, we define $c_d(G)$ to be the number of equivalent $d$-dimensional complex realisations of a $d$-rigid graph $G$ for a given generic realisation, and $c^*_d(G)$ to be the number of equivalent $d$-dimensional complex spherical realisations of $G$ for a given generic spherical realisation. Somewhat surprisingly, these two realisation numbers are not always equal. Recently developed algorithms for computing realisation numbers determined that the inequality $c_2(G) \leq c_2^*(G)$ holds for any minimally 2-rigid graph $G$ with 12 vertices or less. In this paper we confirm that, for any dimension $d$, the inequality $c_d(G) \leq c_d^*(G)$ holds for every $d$-rigid graph $G$. This result is obtained via new techniques involving coning, the graph operation that adds an extra vertex adjacent to all original vertices of the graph.
Original languageEnglish
PublisherarXiv.org
Number of pages35
DOIs
Publication statusPublished - 28 Sept 2023

Bibliographical note

35 pages, 8 figures

Keywords

  • math.CO
  • math.AG
  • 52C25 (Primary) 05C30, 68R10, 68R12 (Secondary)

Fingerprint

Dive into the research topics of 'The number of realisations of a rigid graph in Euclidean and spherical geometries'. Together they form a unique fingerprint.

Cite this