Recognizing graphic matroids

DOI10.1007/BF02579179zbMath0501.05022WikidataQ56430158 ScholiaQ56430158MaRDI QIDQ1172064

P. D. Seymour

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

cocircuitgraphicness testingpolygon-matroid

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (37)

Correlation bounds for fields and matroids ⋮ Trees, grids, and MSO decidability: from graphs to matroids ⋮ Recognizing Even-Cycle and Even-Cut Matroids ⋮ Recognizing a class of bicircular matroids ⋮ Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids ⋮ First order convergence of matroids ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ Adjoints of binary matroids ⋮ Chordal characterization of graphic matroids ⋮ Recognizing Polymatroids Associated with Hypergraphs ⋮ A characterization of a class of non-binary matroids ⋮ Excluding Kuratowski graphs and their duals from binary matroids ⋮ Signed-graphic matroids with all-graphic cocircuits ⋮ Independence and port oracles for matroids, with an application to computational learning theory ⋮ Binary signed-graphic matroids: representations and recognition algorithms ⋮ Inequivalent representations of matroids over prime fields ⋮ On combinatorial properties of binary spaces ⋮ Recognizing even-cycle and even-cut matroids ⋮ Small separations in pinch-graphic matroids ⋮ Decomposition width of matroids ⋮ Certifying non-representability of matroids over prime fields ⋮ On Recognizing Frame and Lifted‐Graphic Matroids ⋮ Unnamed Item ⋮ Separating cocircuits in binary matroids ⋮ On a Generalization of Spikes ⋮ Displaying blocking pairs in signed graphs ⋮ Some open problems on excluding a uniform matroid ⋮ Characterizing bias matroids ⋮ Recognising graphic and matroidal connectivity functions ⋮ The computational complexity of antimatroid properties ⋮ Excluded minors for matroids satisfying Kinser's inequalities ⋮ The Erdös-Pósa property for matroid circuits ⋮ On excluded minors for real-representability ⋮ A short proof of non-GF(5)-representability of matroids ⋮ On the efficiency of representability tests for matroids ⋮ Computational implementation of Fujishige's graph realizability algorithm ⋮ Recent work in matroid representation theory

Cites Work

• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• The computational complexity of matroid properties
• Converting Linear Programs to Network Problems
• Complexity of Matroid Property Algorithms
• Strong maps of geometries

This page was built for publication: Recognizing graphic matroids