Cocircuit graphs and efficient orientation reconstruction in oriented matroids

DOI10.1006/EUJC.2001.0481MaRDI QIDQ5944000zbMATH OpenOpenAlexFDO

Authors Eric Babson, Lukas Finschi, Komei Fukuda

Publication date 19 February 2002

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

Full work available at URL https://infoscience.epfl.ch/record/77402/files/Babson2001_17.pdf

zbMATH Keywords

algorithms in polynomial timecocircuit graphsefficient orientationoriented matroid

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Oriented matroids in discrete geometry (52C40) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Cubic time recognition of cocircuit graphs of uniform oriented matroids
• On the cocircuit graph of an oriented matroid
• Reconstruction of the orientation class of an oriented matroid
• How many circuits determine an oriented matroid?
• A characterization of cocircuit graphs of uniform oriented matroids

Cites work

• A lattice-theoretical characterization of oriented matroids
• A simple way to tell a simple polytope from its graph
• Antipodal graphs and oriented matroids
• scientific article; zbMATH DE number 4092241 (Why is no real title available?)
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• scientific article; zbMATH DE number 1538126 (Why is no real title available?)
• On the cocircuit graph of an oriented matroid
• Oriented Matroids
• Oriented matroids
• Oriented matroids and combinatorial manifolds
• Puzzles and polytope isomorphisms
• Reconstruction of the orientation class of an oriented matroid

Cited in

(21)

• Generation of oriented matroids --- a graph theoretical approach
• On the cocircuit graph of an oriented matroid
• On the number of circuit-cocircuit reversal classes of an oriented matroid
• How many circuits determine an oriented matroid?
• Diameters of cocircuit graphs of oriented matroids: an update
• A characterization of cocircuit graphs of uniform oriented matroids
• A graph-theoretical axiomatization of oriented matroids
• Graph encoding of 2D-gon tilings
• Polynomial time recognition of uniform cocircuit graphs
• A graph-theoretical axiomatization of oriented matroids
• Enumerating neighborly polytopes and oriented matroids
• Reconstruction of a rank 3 oriented matroids from its rank 2 signed circuits
• Checking oriented matroid isomorphism by means of canonical labeling
• Reconstructibility of matroid polytopes
• Reconstruction of the orientation class of an oriented matroid
• Sign conditions for injectivity of generalized polynomial maps with applications to chemical reaction networks and real algebraic geometry
• Purity and Separation for Oriented Matroids
• Cubic time recognition of cocircuit graphs of uniform oriented matroids
• Corners and simpliciality in oriented matroids and partial cubes
• Graphs, skeleta and reconstruction of polytopes
• Circuit-cocircuit reversing systems in regular matroids

This page was built for publication: Cocircuit graphs and efficient orientation reconstruction in oriented matroids

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