Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

E. Babson and L. Finschi and K. Fukuda

2000 January 31

Appeared in: European Journal of Combinatorics, vol. 22 (5), Academic Press, pp. 587-600 (2001)

Download: PDF, PS, PS.gz

Abstract

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. As a 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) >= 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.