## On the Number of Directions in Visibility Representations of Graphs (Extended Abstract)
Kranakis, Evangelos and Krizanc, Danny and Urrutia, Jorge
(1995)
Full text not available from this repository. ## AbstractWe consider visibility representations of graphs in which the vertices are presented 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 \in O are called visible if there exist points x \in A,y \in 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 inidirectional 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. 1980 Mathematics Subject Classification: 68R10, 68U05 CR Categories: F.2.2 Key Words and Phrases: Graph, Number of directions, Polygon, Visibility.
Repository Staff Only: item control page References |