Polynomial Time Recognition of Uniform Cocircuit Graphs

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