Cocircuit graphs and efficient orientation reconstruction in oriented matroids

We consider the cocircuit graph G(M) of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. Asa result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by G(M), but it is determined if M is uniform and the vertices in G(M) are paired if they are associated to negative cocircuits; furthermore the reorientation class of an oriented matroid M with rank(M) greater than or equal to 2 is determined by G(M) if every vertex in G(M) is 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. (C) 2001 Academic Press.