Carleton University
Technical Report TR-248
July 1994
On the Number of Directions in Visibility Representations of Graphs
Abstract
We consider visibility representations of graphs in which the vertices are represented by a collection O of non-overlapping convex regions on the plane. Two points x and y are visible if the straight-line segment xy is not obstructed by any object. Two objects A, B E O are called visible if there exist points x E A, y E B such that x is visible from y. We consider visibility only for a finite set of directions. In such a representation, the given graph is decomposed into a union of unidirectional visibility graphs, for the chosen set of directions. This raises the problem of studying the number of directions needed to represent a given graph. We study this number of directions as a graph parameter and obtain sharp upper and lower bounds for the representability of arbitrary graphs.