2005/10/21 by Florian Pfender, F. Pfender, Pfender, F.
Computer Science · Mathematics · #05C62 (Primary) 05C15 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #math.CO #msc:05C15 #msc:05C62
paper · pdf · doi:10.48550/arxiv.math/0510467
4 pages
arxiv created 2005/10/21 · openalex publication_date 2005/10/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The visibility graph Vis(X) of a discrete point set X in the plane 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, such that the subgraph of Vis(X∪ Z2) 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 six settling a question by Kára, Pór and Wood.