  A point visibility graph is a graph induced by a set of points in the plane,
where every vertex corresponds to a point, and two vertices are adjacent
whenever the two corresponding points are visible from each other, that is, the
open segment between them does not contain any other point of the set. We study
the recognition problem for point visibility graphs: given a simple undirected
graph, decide whether it is the visibility graph of some point set in the
plane. We show that the problem is complete for the existential theory of the
reals. Hence the problem is as hard as deciding the existence of a real
solution to a system of polynomial inequalities. The proof involves simple
substructures forcing collinearities in all realizations of some visibility
graphs, which are applied to the algebraic universality constructions of Mn\"ev
and Richter-Gebert. This solves a longstanding open question and paves the way
for the analysis of other classes of visibility graphs. Furthermore, as a
corollary of one of our construction, we show that there exist point visibility
graphs that do not admit any geometric realization with points having integer
coordinates.
