Visibility Graphs of Point Sets in the Plane |
| |
Authors: | Florian Pfender |
| |
Institution: | (1) MA 6-2, TU Berlin, 10623 Berlin, Germany |
| |
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.
Supported by the DFG Research Center Matheon (FZT86). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|