New Results on a Visibility Representation of Graphs in 3D

Fekete, Sándor P. and Houle, Michael E. and Whitesides, Sue (1996) New Results on a Visibility Representation of Graphs in 3D. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 234-241 (Official URL: http://dx.doi.org/10.1007/BFb0021807).

Full text not available from this repository.

Abstract

This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and two vertices of the graph are adjacent if and only if their corresponding objects see each other by a line of sight parallel to the z-axis that intersects the interiors of the objects. In particular, we represent vertices by unit discs and by discs of arbitrary radii (possibly different for different vertices); we also represent vertices by axis-aligned unit squares, by axis-aligned squares of arbitrary size (possibly different for different vertices), and by axis-aligned rectangles. We present: - a significant improvement (from 102 to 55) of the best known upper bound for the size of cliques representable by retrangles or squares of arbitrary size; - a sharp bound for the representation of cliques by unit squares (K_7 can be represented but K_n for n>7 cannot); - a representation of K_n by unit discs.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021807
Classifications:P Styles > P.900 Visibility
P Styles > P.060 3D
ID Code:136

Repository Staff Only: item control page

References

H. Alt, M. Godau and S. Whitesides. Universal 3-dimensional visibility representations for graphs. See elsewhere in these proceedings.

P. Bose, H. Everett, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer and S. Whitesides. On a visibility representaion for graphs in three dimensions. Proc. Graph Drawing '93, Paris (Sèvres), 1993, pp. 38-39.

P. Bose, H. Everett, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer and S. Whitesides. On a visibility representaion for graphs in three dimensions. Snapshots of Computational and Discrete Geometry, v. 3, eds. D. Avis and P. Bose, McGill University School of Computer Science Technical Report SOCS-94.50, July 1994, pp. 2-25.

R. Cohen, P. Eades, T. Lin and F. Ruskey. Three-dimensional graph drawing. Proc. Graph Drawing '94, Princeton NJ, 1994, Lecture Notes in Computer Science LNCS #894, Springer-Verlag, 1995, pp. 1-11.

F. R. K. Chung. On unimodal subsequences. J. Combinatorial Theory, Series A, v. 29, 1980, pp. 267-279.

A. Dean and J. Hutchison. Rectangle visibility representations of bipartite graphs. Proc. Graph Drawing '94, Princeton NJ, 1994. Lecture Notes in Computer Science LNCS #894, Springer-Verlag, 1995, pp. 159-166.

J. M. Hammersley. A few seedlings of research. Proc. 6th Berkeley Symp. Math. Stat. Prob., U. of California Press, 1972, pp. 345-394.

H. Koike. An application of three-dimensional visualization to object-oriented programming. Proc. of Advanced Visual Interfaces AVI '92, Rome, May 1992, v. 36 of World Scientific Series in Computer Science, 1992, pp. 180-192.

E. Kranakis, D. Krizanc and J. Urrutia. On the number of directions in visibility representations of graphs. Proc. Graph Drawing '94, Princeton NJ, 1994, Lecture Notes in Computer Science LNCS #894, Springer-Verlag, 1995, pp. 167-176.

J. Mackinley, G. Robertson and S. Card. Cone trees: animated 3d visualizations of hierarchical information. Proc. of the SIGCHI Conf. on Human Factors in Computing, 1991, pp. 189-194.

K. Romanik. Directed VR- representable graphs have unbounded dimension. Proc. Graph Drawing '94, Princeton, NJ, 1994, Lecture Notes in Computer Science LNCS #894, Springer-Verlag, 1995, pp. 177-181.

R. Tamassia and I. Tollis. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom. v. 1, 1986, pp. 321-341.

S. Wismath. Characterizing bar line-of-sight graphs. Proc. ACM Symp. on Computational Geometry, 1985, pp. 147-152.