Cubic time recognition of cocircuit graphs of uniform oriented matroids (Q607364): Difference between revisions

Uniform oriented matroids are characterized by \textit{R. Cordovil, K. Fukuda} and \textit{A. Guedes de Oliveira}, ``On the cocircuit graph of an oriented matroid,'' Discrete Comput. Geom. 24, No.\,2--3, 257--265 (2000; Zbl 0958.52016)] in terms of cocircuit graphs with an antipodal labeling and by \textit{J. J. Montellano-Ballesteros} and \textit{R. Strausz} [``A characterization of cocircuit graphs of uniform oriented matroids,'' J. Comb. Theory, Ser. B 96, No. 4, 445--454 (2006; Zbl 1109.52016)] via sign-labeled cocircuit graphs. In the paper under review the concept of crabbed connectivity is introduced and a strengthened version of the main theorem in the above cited work of Montellano-Ballesteros and Strausz is proved and used to provide an algorithm that decides whether a given graph is the cocircuit graph of a uniform oriented matroid. The running time is better than the one given in [\textit{E. Babson, L. Finschi} and \textit{K. Fukuda}, ``Cocircuit graphs and efficient orientation reconstruction in oriented matroids,'' Eur. J. Comb. 22, No.\,5, 587--600 (2001; Zbl 0988.52032)]. Some open problems to further improve the running time are formulated in terms of the diameter of the cocircuit graph and antipodal labellings.