Generation of Oriented Matroids - A Graph TheoreticalApproach

Lukas Finschi and Komei Fukuda

2000 October 31

Appeared in: Discrete & Computational Geometry, vol. 27, 2002, pages 117-136 (2002)

Download: PDF, PS, PS.gz

Abstract

We discuss methods for the generation of oriented matroids and of isomorphism classes of oriented matroids. Our methods are based on single element extensions and graph theoretical representations of oriented matroids, and all these methods work in general rank and for non-uniform and uniform oriented matroids as well. We consider two types of graphs, cocircuit graphs and tope graphs, and discuss the single element extensions in terms of localizations which can be viewed as partitions of the vertex sets of the graphs. Whereas localizations of the cocircuit graph are well characterized, there is no graph theoretical characterization known for localizations of the tope graph. In this paper we prove a connectedness property for tope graph localizations and use this for the design of algorithms for the generation of single element extensions by use of tope graphs. Furthermore we discuss similar algorithms which use the cocircuit graph. The characterization of localizations of cocircuit graphs finally leads to a backtracking algorithm which is a simple and efficient method for the generation of single element extensions. We compare this method with a recent algorithm of Bokowski and Guedes de Oliveira for uniform oriented matroids.