On the Number of Directions in Visibility Representations of Graphs (Extended Abstract)Kranakis, Evangelos and Krizanc, Danny and Urrutia, Jorge (1995) On the Number of Directions in Visibility Representations of Graphs (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 167176(Official URL: http://dx.doi.org/10.1007/3540589503_368). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_368
AbstractWe consider visibility representations of graphs in which the vertices are presented by a collection O of nonoverlapping convex regions on the plane. Two points x and y are visible if the straightline 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.
Actions (login required)
