A constructive characterisation of circuits in the simple (2,2)-sparsity matroid

DOI10.1016/J.EJC.2014.05.009zbMATH Open1300.05055arXiv1202.3294OpenAlexW2963452381MaRDI QIDQ404444FDOQ404444

Anthony Nixon

Publication date: 4 September 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We provide a constructive characterisation of circuits in the simple (2,2)-sparsity matroid. A circuit is a simple graph G=(V,E) with |E|=2|V|-1 and the number of edges induced by any $XsubsetneqV$ is at most 2|X|-2. Insisting on simplicity results in the Henneberg operation being enough only when the graph is sufficiently connected. Thus we introduce 3 different join operations to complete the characterisation. Extensions are discussed to when the sparsity matroid is connected and this is applied to the theory of frameworks on surfaces to provide a conjectured characterisation of when frameworks on an infinite circular cylinder are generically globally rigid.

Full work available at URL: https://arxiv.org/abs/1202.3294

Recommendations

• A constructive characterisation of circuits in the simple (2,1)-sparse matroid
• On the two-dimensional generic rigidity matroid and its dual
• Global rigidity of generic frameworks on the cylinder
• On characterizations of rigid graphs in the plane using spanning trees
• On the 2-sum in rigidity matroids

zbMATH Keywords

theory of frameworks on surfaces

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Connected rigidity matroids and unique realizations of graphs
• Pebble game algorithms and sparse graphs
• Generic global rigidity
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• Conditions for Unique Graph Realizations
• Title not available (Why is that?)
• Decomposition of Finite Graphs Into Forests
• The Union of Matroids and the Rigidity of Frameworks
• A Characterization of Generically Rigid Frameworks on Surfaces of Revolution
• Title not available (Why is that?)
• Necessary conditions for the generic global rigidity of frameworks on surfaces
• Rigidity of Frameworks Supported on Surfaces
• An Inductive Construction of (2,1)-tight Graphs
• Constructive characterizations for packing and covering with trees
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• On the 2-sum in rigidity matroids
• A note on \([k,l]\)-sparse graphs
• Title not available (Why is that?)

Cited In (3)

• Global rigidity of generic frameworks on the cylinder
• Necessary conditions for the generic global rigidity of frameworks on surfaces
• Stress matrices and global rigidity of frameworks on surfaces

This page was built for publication: A constructive characterisation of circuits in the simple \((2,2)\)-sparsity matroid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404444)