1. Visibility Graphs of Point Sets in the Plane.
- Author
-
Florian Pfender
- Subjects
- *
GRAPHIC methods , *ISOMORPHISM (Mathematics) , *MATHEMATICAL category theory , *GROUP theory - Abstract
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]
- Published
- 2008
- Full Text
- View/download PDF