Cubic time recognition of cocircuit graphs of uniform oriented matroids

We present an algorithm which takes a graph as input and decides in cubic time whether 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.