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: http://dx.doi.org/10.1007/3-540-58950-3_366).

Full text not available from this repository.

Abstract

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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/143

Actions (login required)

View Item View Item