TR-248: On the Number of Directions in Visibility Representations of Graphs
Carleton University
Technical Report TR-248
July 1994
On the Number of Directions in Visibility Representations of Graphs
Evangelos Kranakis, Danny Krizanc, Jorge Urrutia
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.