Click on the figure to download the paper in pdf format.
Cubic time recognition of cocircuit graphs of
uniform oriented matroids.
Stefan Felsner,
Ricardo Gómez,
Kolja Knauer,
Juán José Montellano-Ballesteros and
Ricardo Strausz.
European Journal of Combinatorics 32 (2011) 60-66.
Abstract.
We present an algorithm which takes a graph as input and decides
in cubic time if the graph is the cocircuit graph of a uniform oriented
matroid. In the affirmative case the algorithm returns the set of signed
cocircuits of the oriented matroid. This improves an algorithm proposed
by Babson, Finschi and Fukuda.
Moreover we strengthen a result of Montellano-Ballesteros and Strausz
characterizing cocircuit graphs of uniform oriented matroids in terms of
crabbed connectivity.
Click on the figure to download the paper in pdf format.