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, Princeton, New Jersey, USA , 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
ID Code:143

Repository Staff Only: item control page


Abello, J., Egecioglu,O.: Visibility Graphs of Staircase Polygons with Uniform Step Length, International Giornal of Discrete and Computational Geometry, 3 (1993) pp. 27-37.

Abello, J., Hua, L., Pisupati, C.: On Visibility Graphs of Simple Polygons, Congressus Numerantium, 90 (1992), pp. 119-128.

Abello, J., Egecioglu, O., Kumar, K.: Visibility Graphs of Staircase Polygons and the Weak Bruhat Order I : From Visibility Graphs to Maximal Chains, Discrete and Computational Geometry, Accepted (pending revisions).

Abello, J., Kumar, K.: Visibility Graphs and Oriented Matroids (Long Version), Manuscript.

Aronov, B.: On the Geodesic Voronoi Diagram of Point Sites in a Simple Polygon, Algorithmica, 4 (1989) pp. 109-140.

Bokowski, J., Sturmfels, B.: Computational Synthetic Geometry, Lecture Notes in Mathematics, 1335 (1989), Springer- Verlag, New York.

Canny, J.: Some Algebraic and Geometric Computations in PSPACE, Proceedings of the 20th ACM Symposium on Theory of Computing, 1988, pp. 460-467.

Coullard, C. and Lubiw, A.: Distance Visibility Graphs, Proceedings of the ACM Symposium on Computational Geometry, 1991, pp. 290-302.

Everett, H.: Visibility Graph Recognition, PhD Dissertation, Department of Computer Science, University of Toronto, 1990.

Folkman, J., Lawrence, J.: Oriented Matroids, Journal of Combinatorial Theory (B), 25 (1978), pp. 199-236.

Ghosh, S.K.: On Recognizing and Characterizing Visibility Graphs of Simple Polygons, Lecture Notes in Computer Science, 318 (1988), pp. 132-139, Springer-Verlag, New York

Goodman, J.E., Pollak, R.: Semispaces of Configurations, Cell Complexes of Arrangements,In: Journal of Combinatorial Theory (A), (37) pp. 84-102, 1984.

Greene, N., Kass, M. and Miller, G.: Hierarchical Z-buffer Visibility, SIGGRAPH 93 Proceedings, pp 231-238, 1993.

Kumar, K.: Combinatorial Aspects of Point Visibility, PhD. Dissertation, Dept. of Computer Science, Texas A&M University, August 1993.

Lawrence, J.: Oriented Matroids and Multiply Ordered Sets, Linear Algebra and its Applications, 48 (1982) pp. 1-12.

Lozano-Perez, T. and Wesley, M.A.: An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles, In: Communications of the ACM, (22) pp. 560-570, 1979.

Mnev,N.E.: The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytope Varieties, Lecture Notes in Mathematics, 1346 (1988), pp. 527-544, Springer-Verlag, New York.

O'Rourke, J.: Art Gallery Theorems and Algorithms, Oxford University Press, 1987.

O'Rourke, J.: The Computational Geometry Column, SIGACT News, (1992).

Shor,P.W.: Stretchability of Pseudolines is NP-Hard, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 4 (1991), pp. 531-554.

Teller, S., Hanrahan, P.: Global Visibility Algorithms for Illumination Computations, SIGGRAPH 93 Proceedings, pp 239-246, 1993.