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

DOI10.1016/J.EJC.2014.05.009MaRDI QIDQ404444zbMATH OpenOpenAlexFDO

Authors Anthony Nixon

Publication date 4 September 2014

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

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

zbMATH Keywords

theory of frameworks on surfaces

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

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.

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

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 30657 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• A characterization of generically rigid frameworks on surfaces of revolution
• A note on \([k,l]\)-sparse graphs
• A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid.
• An algorithm for two-dimensional rigidity percolation: The pebble game
• An inductive construction of \((2,1)\)-tight graphs
• Conditions for Unique Graph Realizations
• Connected rigidity matroids and unique realizations of graphs
• Constructive characterizations for packing and covering with trees
• Decomposition of Finite Graphs Into Forests
• Generic global rigidity
• Necessary conditions for the generic global rigidity of frameworks on surfaces
• On graphs and rigidity of plane skeletal structures
• On the 2-sum in rigidity matroids
• On the Problem of Decomposing a Graph into n Connected Factors
• Pebble game algorithms and sparse graphs
• Rigidity of Frameworks Supported on Surfaces
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(6)

• A constructive characterisation of circuits in the simple (2,1)-sparse matroid
• Global rigidity of generic frameworks on the cylinder
• Necessary conditions for the generic global rigidity of frameworks on surfaces
• Sparsity and connectivity of medial graphs: Concerning two edge-disjoint Hamiltonian paths in planar rigidity circuits
• Stress matrices and global rigidity of frameworks on surfaces
• An inductive construction of \((2,1)\)-tight graphs

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)