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.
Structural aspects of point visibility graphs have been studied by K 'ara, P 'or, and Wood @cite_13 , P 'or and Wood @cite_14 , and @cite_0 . Many fascinating open questions revolve around the big-line-big-clique conjecture, stating that for all @math , there exists an @math such that every finite set of at least @math points in the plane contains either @math pairwise visible points or @math collinear points.
@cite_0 @cite_14 @cite_13
1963903160 2103602888 2170459217
The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesnik (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71–93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesnik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)≤deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least @math , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree. This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane. The visibility graph V(P) of a point set P R2 has vertex set P, such that two points v,w ∈ P are adjacent whenever there is no other point in P on the line segment between v and w. We study the chromatic number of V(P). We characterise the 2- and 3-chromatic visibility graphs. It is an open problem whether the chromatic number of a visibility graph is bounded by its clique number. Our main result is a super-polynomial lower bound on the chromatic number (in terms of the clique number).