Orthogonal 3-D Graph Drawing

Biedl, Therese and Shermer, Thomas and Whitesides, Sue and Wismath, Stephen (1998) Orthogonal 3-D Graph Drawing. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 76-86 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_52).

Full text not available from this repository.

Abstract

This paper studies 3-D orthogonal grid drawings for graphs of arbitrary degree, K_{n} in particular, with vertices drawn as boxes. It establishes an asymptotic lower bound for the volume of the bounding box of such drawings and exhibits a construction that achieves this bound. No edge route in this unconstrained construction bends more than three times. For drawings constrained to have at most k bends on any edge route, simple constructions are given for k=1 and k=2. The unconstrained construction handles the k \geq 3 cases, while for k=0 (no bends), it is proved here that not all graphs can be drawn.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_52
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:176

Repository Staff Only: item control page

References

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. Proc. Graph Drawing '93, Paris, 1993, 38-39.

T. Biedl, B. Madden, and I. Tollis. The three-phase method: A unified approach to orthogonal graph drawing. In these proceedings.

F. Brandenburg, ed. Symposium on Graph Drawing '95, Passau, Germany, Springer-Verlag LNCS 1027, 1996.

P. Eades, A. Symvonis and S. Whitesides. Two algorithms for three dimensional orthogonal graph drawing. In S. North, ed. Symposium on Graph Drawing '96, Berkeley , California, Springer Verlag LNCS 1190, 1997, 139-154.

S. Fekete, M. Houle and S. Whitesides. New results on a visibility representation of graphs in 3d. In [Bra96], 234-241.

U. Fößmeier and M. Kaufmann. Drawing high degree graphs with low bend numbers. In [Bra96], 254-266.

R. Graham, B.L. Rothschild and J. Spencer. Ramsey Theory. John Wiley, 1980.

A. Papakostas and I. Tollis. High-degree orthogonal drawings with small grid-size nad few bends. In 5th Workshop on Algorithms and Data Structures, Springer Verlag LNCS, 1997. To appear.

A. Papakostas and I. Tollis. Incremental orthogonal graph drawing in three dimensions. In these proceedings.

A. Rosenberg. Three-dimensional VLSI: A case study. Journal of the Association of Computing Machinery, 30 (3), 1983, 397-416.

R. Tamassia and I. Tollis. A unified approach to visibility representations of planar graphs. J. of Discrete and Computational Geometry 1, 1986, 321-341.

S.K. Wismath. Characterizing bar line-of-sight graphs. Proc. of the 1st ACM Symp. on Computational Geometry, Baltimore, Maryland, USA, 1985, 147-152.

M. Yannakakis, Embedding planar graphs in four pages. 18th Annual ACM Symposium on Theory of Computing, J. Comput. System Sci. 38 (1989), no. 1, 36-67.