Visibility Graphs and Oriented Matroids (Extended Abstract)

Abello, James and Kumar, Krishna (1995) Visibility Graphs and Oriented Matroids (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD, October 10–12, 1994 , pp. 147-158(Official URL:

Full text not available from this repository.


This paper describes a new set of necessary conditions for a given graph to be the visibility graph of a simple polygon. For every graph satisfying these conditions we show that a uniform rank 3 oriented matroid can be constructed in polynomial time, which if affinely co- ordinatizable would yield a simple polygon whose visibility graph is isomorphic to the given graph. This will in turn offer the first characterization of this class of graphs.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_366
Classifications: Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item