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, Princeton, New Jersey, USA , 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
ID Code:145

Repository Staff Only: item control page

References

G. Di Battista and P. Eades and R. Tamassia and I. G. Tollis, "Algorithms for Drawing Graphs: Ana Annotated Bibliography", Comput. Geom. Theory Appl, to appear. (Preprint available by anonymous ftp from ftp.cs.brown.edu:pub/papers/compgeo/.)

P. Bose, H. Everett, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides, "On a Visibility Representation for Graphs in Three Dimensions" (abstract), ALCOM International Workshop on Graph Drawing and Topological Graph Algorithms, Paris, September 26-29, 1993, pp. 53-54. (Also, in McGill Technical Report "Snapshots of Computational and Discrete Geometry", 1994.)

F. Harary, "Graph Theory", Addison-Wesley Publishing Company, 1969.

L. S. Heath and S. Istrail, "The Pagenumber of Genus g Graphs is O(g)", in STOC87, pages 388-397.

J. O'Rourke, "Computational Geometry Column 18", International Journal of Computational Geometry & Applications, pp. 107-113, Vol. 3, No. 1, 1993.

I. Rival and J. Urrutia, "Representing Orders on the Plane by Translating Convex Figures", Order 4 (1988), 319-329.

I. Rival and J. Urrutia, "Representing Orders by Moving Figures in Space", Discrete Mathematics 109 (1992), 255-263.

R. Tamassia and I. G. Tollis, " A Unified Approach to Visibility Representations of Planar Graphs". Discrete Comput. Geom. 1:321-341, 1986.

R. Tamassia and I. G. Tollis, "Plane Representations of Graphs and Visibility Between Parallel Segments", TR ACT-37, Univ. of Ill., Urbanna Champaign, 1985.

H. Warren, "Lower Bounds for Approximation by Nonlinear Manifolds", Transactions of the AMS 133 (1968), 167-178.

S. K. Wismath, "Characterizing Bar Line-of-sight Graphs", Proc. 1st Annu. ACM Sympos. Comput. Geom., pp. 147-152.

M. Yannakakis, "Four Pages are Necessary and Sufficient for Planar Graphs", in STOC86, pages 104-108.