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. 167-176(Official URL: http://dx.doi.org/10.1007/3-540-58950-3_368).

Full text not available from this repository.

Abstract

We 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_368
Classifications: P Styles > P.900 Visibility
Z Theory > Z.500 Representations
URI: http://gdea.informatik.uni-koeln.de/id/eprint/145

Actions (login required)

View Item View Item