Visibility Graphs of Point Sets in the Plane.

Abstract  The visibility graph of a discrete point set X⊂ℝ2 has vertex set X and an edge xy for every two points x,y∈X whenever there is no other point in X on the line segment between x and y. We show that for every graph G, there is a point set X∈ℝ2, such that the subgraph of induced by X is isomorphic to G. As a consequence, we show that there are visibility graphs of arbitrary high chromatic number with clique number 6 settling a question by Kára, Pór and Wood. [ABSTRACT FROM AUTHOR]