Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

We consider the cocircuit graph GMof an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by GM, but it is determined if M is uniform and the vertices in GMare paired if they are associated to negative cocircuits; furthermore the reorientation class of an oriented matroid M with rank(M) ≥ 2 is determined by GMif every vertex in GMis labeled by the zero support of the associated cocircuit. In this paper we show that the isomorphism class of a uniform oriented matroid is determined by the cocircuit graph, and we present polynomial algorithms which provide constructive proofs to all these results. Furthermore it is shown that the correctness of the input of the algorithms can be verified in polynomial time.