On recognizing and characterizing visibility graphs of simple polygons

In this paper we establish four necessary conditions for recognizing visibility graphs of simple polygons and conjecture that these conditions are sufficient. We present an O(n<SUP>2</SUP>)-time algorithm for testing the first and second necessary conditions and leave it open whether the third and fourth necessary conditions can be tested in polynomial time. We also show that visibility graphs of simple polygons do not possess the characteristics of a few special classes of graphs