A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
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.
- scientific article; zbMATH DE number 17636
- Connected rigidity matroids and unique realizations of graphs
- On spaces of infinitesimal motions and three dimensional Henneberg extensions
- Characterizing generic global rigidity
- Vertex splitting, coincident realisations, and global rigidity of braced triangulations
- Conditions for Unique Graph Realizations
- scientific article; zbMATH DE number 3917126 (Why is no real title available?)
- scientific article; zbMATH DE number 17636 (Why is no real title available?)
- scientific article; zbMATH DE number 67319 (Why is no real title available?)
- scientific article; zbMATH DE number 501471 (Why is no real title available?)
- scientific article; zbMATH DE number 1757954 (Why is no real title available?)
- scientific article; zbMATH DE number 952952 (Why is no real title available?)
- scientific article; zbMATH DE number 3308985 (Why is no real title available?)
- Linking \((n-2)\)-dimensional panels in \(n\)-space. I: \((k-1,k)\)-graphs and \((k-1,k)\)-frames
- On graphs and rigidity of plane skeletal structures
- Rigidity and energy
- Rigid tensegrity labelings of graphs
- Equivalent realisations of a rigid graph
- Planar minimally rigid graphs and pseudo-triangulations
- Connected rigidity matroids and unique realizations of graphs
- Assur decompositions of direction-length frameworks
- Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
- Phase retrieval of complex and vector-valued functions
- Generically globally rigid graphs have generic universally rigid frameworks
- Global rigidity of periodic graphs under fixed-lattice representations
- Sufficient conditions for the global rigidity of graphs
- Inductive constructions for frameworks on a two-dimensional fixed torus
- Addressing agent loss in vehicle formations and sensor networks
- Operations preserving global rigidity of generic direction-length frameworks
- Robust tensegrity polygons
- A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid
- Boundedness, rigidity and global rigidity of direction-length frameworks
- Balanced generic circuits without long paths
- Periodic rigidity on a variable torus using inductive constructions
- Generating all rigidity circuits on at most 10 vertices and all Assur graphs on at most 11 vertices
- Self-dual polyhedra of given degree sequence
- Globally linked pairs of vertices in rigid frameworks
- One brick at a time: a survey of inductive constructions in rigidity theory
- 1-extensions and global rigidity of generic direction-length frameworks
- Good orientations of unions of edge‐disjoint spanning trees
- Flexible circuits in the d‐dimensional rigidity matroid
- Good acyclic orientations of 4‐regular 4‐connected graphs
- Computing Circuit Polynomials in the Algebraic Rigidity Matroid
- Four-regular graphs with extremal rigidity properties
- Augmenting the rigidity of a graph in \(\mathbb R^{2}\)
- Enumerating combinatorial resultant trees
- Maximum likelihood thresholds via graph rigidity
- On self-duality and unigraphicity for 3-polytopes
- Generic global rigidity of body-bar frameworks
- Combinatorial resultants in the algebraic rigidity matroid
- Combining globally rigid frameworks
- Geometry of configuration spaces of tensegrities
- On constructive characterizations of (k,l)-sparse graphs
- Globally rigid circuits of the direction-length rigidity matroid
- Global rigidity: The effect of coning
- Combinatorial characterization of the Assur graphs from engineering
- Rigidity, global rigidity, and graph decomposition
This page was built for publication: A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405103)
