On Visibility Graphs of Point Sets in the Plane
| dc.creator | Pfender, F. | |
| dc.date | 2005-10-21 | |
| dc.date.accessioned | 2026-07-07T06:47:46Z | |
| dc.date.available | 2026-07-07T06:47:46Z | |
| dc.description | 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\in 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\cup Z^2) 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. | |
| dc.description | 4 pages | |
| dc.identifier | https://arxiv.org/abs/math/0510467 | |
| dc.identifier | http://arxiv.org/abs/math/0510467 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/103765 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C62 (Primary) 05C15 (Secondary) | |
| dc.title | On Visibility Graphs of Point Sets in the Plane | |
| dc.type | text |