Spectral conditions for graph rigidity in the Euclidean plane

Sebastian M. Cioabă, Sean Dewar, Xiaofeng Gu

Research output: Contribution to journalArticle (Academic Journal)peer-review

4 Citations (Scopus)
14 Downloads (Pure)

Abstract

Rigidity is the property of a structure that does not flex. It is well studied in discrete geometry and mechanics, and has applications in material science, engineering and biological sciences. A bar-and-joint framework is a pair $(G,p)$ of graph $G$ together with a map $p$ of the vertices of $G$ into the Euclidean plane. We view the edges of $(G, p)$ as bars and the vertices as universal joints. The vertices can move continuously as long as the distances between pairs of adjacent vertices are preserved. The framework is rigid if any such motion preserves the distances between all pairs of vertices. In 1970, Laman obtained a combinatorial characterization of rigid graphs in the Euclidean plane. In 1982, Lov\'asz and Yemini discovered a new characterization and proved that every $6$-connected graph is rigid. Combined with a characterization of global rigidity, their proof actually implies that every 6-connected graph is globally rigid. Consequently, if Fiedler's algebraic connectivity is greater than 5, then $G$ is globally rigid. In this paper, we improve this bound and show that for a graph $G$ with minimum degree $\delta\geq 6$, if its algebraic connectivity is greater than $2+\frac{1}{\delta -1}$, then $G$ is rigid and if its algebraic connectivity is greater than $2+\frac{2}{\delta -1}$, then $G$ is globally rigid. Our results imply that every connected regular Ramanujan graph with degree at least $8$ is globally rigid. We also prove a more general result giving a sufficient spectral condition for the existence of $k$ edge-disjoint spanning rigid subgraphs. The same condition implies that a graph contains $k$ edge-disjoint spanning $2$-connected subgraphs. This result extends previous spectral conditions for packing edge-disjoint spanning trees.
Original languageEnglish
Article number112527
JournalDiscrete Mathematics
Volume344
Issue number10
DOIs
Publication statusPublished - 1 Oct 2021

Bibliographical note

15 pages, 1 figure; this updated version includes a new co-author and new results involving global rigidity

Keywords

  • math.CO
  • math.GT
  • 05C50, 05C70

Fingerprint

Dive into the research topics of 'Spectral conditions for graph rigidity in the Euclidean plane'. Together they form a unique fingerprint.

Cite this