|
The recognition problem for visibility graphs is, given a graph, to determine whether this graph is the visibility graph of a simple polygon. It is not known whether this problem could be solved in polynomial time. A necessary condition for a graph to be a visibility graph is the existence of at least one Hamiltonian cycle, corresponding to the boundary of the polygon. Tutte proved that every 4-connected planar graph has a Hamiltonian cycle. However, in this thesis we shall prove that no 4-connected planar graph could be a visibility graph. We shall also give the necessary and sufficient conditions for a polygon to have a planar visibility graph.
|