Universal 3-Dimensional Visibility Representations Graphs

Alt, Helmut and Godau, Michael and Whitesides, Sue (1996) Universal 3-Dimensional Visibility Representations Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 8-19 (Official URL: http://dx.doi.org/10.1007/BFb0021785).

Full text not available from this repository.

Abstract

This paper studies 3-dimensional visibility representations of graphs in which objects in 3-d correspond to vertices and vertical visibilities between these objects correspond to edges. We ask which classes of simple objects are universal, i.e. powerful enough to represent all graphs. In particular, we show that there is no constant k for which the class of all polygons having k or fewer sides is universal. However, we show by construction that every graph on n vertices can be represented by polygons each having at most 2n sides. The constrution can be carried out by an O(n^2) algorithm. We also study the universality of classes of simple objects (translates of a single, not necessarily polygonal object) relative to cliques K_n and similarly relative to complete bipartite graphs K_{n,m}.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021785
Classifications:Z Theory > Z.500 Representations
P Styles > P.900 Visibility
P Styles > P.060 3D
ID Code:137

Repository Staff Only: item control page

References

N. Alon, "The number of polytopes, configurations and real matroids", Mathematika 33 (1986). pp. 62-71

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", in 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

J. Canny, B. Donald and E. K. Ressler, "A rational rotation method for robust geometric algorithms", Proc. 8th ACM Symp. Comput. Geom., 1992, 251-260.

G. Di Battista, P. Eades, R. Tamassia and I. Tollis, "Algorithms for drawing graphs: an annotated bibliography", Computational Geometry Theory and Applications, v. 4, 1994, 235-282. Also available from wilma.cs.brown.edu by ftp.

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

P. Erdös, Gy. Szekeres, "A Combinatorial Problem in Geometry", Compositio Math. 2, 1935, 463-470.

S. Felsner, personal communication, 1995.

S. Fekete, M. Houle and S. Whitesides, "New results on a visibility representation of graphs in 3D," in Proc. Symposium on Graph Drawing (GD '95), Passau, Germany, 1995, Springer-Verlag LNCS series (these proceedings).

B. Grünbaum, "On a Conjecture of H. Hadwiger", Pacific J. Math., 11, 215-219.

H. Hadwiger, "Über Treffzahlen bei translationsgleichen Eikörpern", Arch. Math., Vol. VIII, 1957, 212-213.

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

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

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

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