A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
type: Item
instance of: scholarly article
title: A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
zbMATH Open document ID: 1036.05047
DOI: 10.1016/S0095-8956(02)00037-0
author: Alex R. Berg
author: Tibor Jordán
published in: Journal of Combinatorial Theory. Series B
publication date: 2003-08-25T00:00:00Z
review text: A graph \(G= (V,E)\) is called a generic circuit if \(| E|= 2| V|- 2\) and every \(X\subset V\) with \(2\leq| X|\leq| V|- 1\) satisfies \(i(X)\leq 2| X|-3\) where \(i(X)\) is the number of edges induced by \(X\). The operator extension subdivides an edge \(uw\) of a graph by a new vertex \(v\) and adds a new edge \(uz\) for some vertex \(z\neq u,w\). The authors prove that every 3-connected generic circuit can be obtained from \(K_4\) by a sequence of extensions. This was conjectured by R. Connelly [see i.e. \textit{W. Whiteley}, Contemp. Math. 197, 171--311 (1996; Zbl 0860.05018)]. As a corollary the authors obtain a special case of a conjecture of \textit{B. Hendrickson} [SIAM J. Comput. 21, 65--84 (1992; Zbl 0756.05047)] on generically globally rigid graphs.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 1970678
zbMATH Keywords: generic circuit
zbMATH Keywords: globally rigid graph
reviewed by: Michael Hager
MaRDI profile type: Publication
cites work: Q5589866
cites work: Rigidity and energy
cites work: Q3974964
cites work: Q4537742
cites work: Q4279195
cites work: Conditions for Unique Graph Realizations
cites work: On graphs and rigidity of plane skeletal structures
cites work: Linking \((n-2)\)-dimensional panels in \(n\)-space. I: \((k-1,k)\)-graphs and \((k-1,k)\)-frames
cites work: Q3694165
cites work: Q4012027
cites work: Q4717849
description: scientific article; zbMATH DE number 1970678