Logo

Login

Orthogonal 3-D Graph Drawing

Biedl, Therese and Shermer, Thomas and Whitesides, Sue and Wismath, Stephen (1998) Orthogonal 3-D Graph Drawing. [Conference Paper]

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
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
Deposited By:Martinez Leon, Victoria
Deposited On:26 Oct 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

[BEFLMRSW93] 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.

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

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

[ESW97] 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.

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

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

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

[PT96] 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.

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

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

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

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

[Yan89] 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.