9304081 Abello This project is concerned with the problem of deciding if a given graph is the visibility graph of a simple polygon on the plane. This problem is known to be in PSPACE but it is not known to be NP-HARD. In fact even proving membership in NP appears to be non trivial. A novel approach to studying properties of visibility graphs of simple polygons is being pursued based on the result that visibility graphs of simple polygons can be derived in a purely combinatorial manner from the representations of their underlying point configurations by chains in the weak Bruhat order of the symmetric group. One of the objectives is to obtain a characterization of visibility graphs of simple polygons in terms of a class of graphs derived from chains in the weak Bruhat order of the symmetric group. Such a characterization would prove membership in NP and also provide a purely combinatorial algorithm for the visibility graph recognition problem. In addition, the combinatorial and algorithmic relationships between visibility graph recognition and fundamental problems in Computational Synthetic geometry, such as oriented matroid representation and circular sequence realization are being explored.
