Visibility Graph - Characterization

Characterization

The visibility graph of a simple polygon has the polygon's vertices as its point locations, and the exterior of the polygon as the only obstacle. Visibility graphs of simple polygons must be Hamiltonian graphs: the boundary of the polygon forms a Hamiltonian cycle in the visibility graph. However, the precise characterization of these graphs is unknown. It is a major open problem in this area whether there exists a polynomial time algorithm that can take as input a graph (possibly together with a fixed Hamiltonian in the cycle that is to correspond to the boundary) and produce as output a polygon for which it is the visibility graph, if such a polygon exists.