  Visibility graph of a polygon corresponds to its internal diagonals and
boundary edges. For each vertex on the boundary of the polygon, we have a
vertex in this graph and if two vertices of the polygon see each other there is
an edge between their corresponding vertices in the graph. Two vertices of a
polygon see each other if and only if their connecting line segment completely
lies inside the polygon, and they are externally visible if and only if this
line segment completely lies outside the polygon. Recognizing visibility graphs
is the problem of deciding whether there is a simple polygon whose visibility
graph is isomorphic to a given input graph. This problem is well-known and
well-studied, but yet widely open in geometric graphs and computational
geometry.
  Existential Theory of the Reals is the complexity class of problems that can
be reduced to the problem of deciding whether there exists a solution to a
quantifier-free formula F(X1,X2,...,Xn), involving equalities and inequalities
of real polynomials with real variables. The complete problems for this
complexity class are called Existential Theory of the Reals Complete.
  In this paper we show that recognizing visibility graphs of polygons with
holes is Existential Theory of the Reals Complete. Moreover, we show that
recognizing visibility graphs of simple polygons when we have the internal and
external visibility graphs, is also Existential Theory of the Reals Complete.
