The \(d\)-dimensional rigidity matroid of sparse graphs
type: Item
instance of: scholarly article
title: The \(d\)-dimensional rigidity matroid of sparse graphs
zbMATH Open document ID: 1070.05022
author: Tibor Jordán
author: Bill Jackson
published in: Journal of Combinatorial Theory. Series B
publication date: 2005-09-28T00:00:00Z
review text: For a graph \(G\) with vertices of degree \(d+1\) or \(d+2\) the rank funcion of the \(d\)-dimensional generic rigidity matroid \(\mathcal{R}_d (G)\) is determined via a min-max formula. For even \(d\) it is shown that the edge set \(E(G)\) is independent in \(\mathcal{R}_d (G)\) if every subset \(X\) of the vertex set containing at least two vertices induces a subgraph containing at most \(1/2[(d+2)| X| -(2d+2)]\) edges. The authors conjecture that this holds also for odd \(d\) and provide a proof for \(d=3\). Moreover, the authors use the independence result for even \(d\), to show that if the connectivity of \(G\) is large in comparison to \(d\) then \(E(G)\) has large rank in \(\mathcal{R}_d (G)\). The case \(d=4\) is used to show that a 10-connected graph can be made rigid in 3-space by pinning approximately three quarters of its vertices. The Lovász and Yemini conjecture that 12-connectivity might be sufficient to insure the rigidity of a graph in 3-space is still open.
reviewed by: Brigitte Servatius
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 2209138
zbMATH Keywords: framework
zbMATH Keywords: Laman graphs
MaRDI profile type: Publication
full work available at URL: j.jctb.2005.03.004
OpenAlex ID: W2079335274
cites work: Algorithms for the d-Dimensional Rigidity Matroid of Sparse Graphs
cites work: Source location with rigidity and tree packing requirements
cites work: Q4279195
cites work: Connected rigidity matroids and unique realizations of graphs
cites work: On graphs and rigidity of plane skeletal structures
cites work: Matroid matching and some applications
cites work: On Generic Rigidity in the Plane
cites work: On the Computational Complexity of a Rigidity Problem
cites work: Matroid theory and its applications in electric network theory and in statics
cites work: Q3330973
cites work: Q4717849
DOI: 10.1016/J.JCTB.2005.03.004
description: scientific article