Proximity Drawings: Three Dimensions Are Better than Two (Extended Abstract)

Penna, Paolo and Vocca, Paola (1998) Proximity Drawings: Three Dimensions Are Better than Two (Extended Abstract). In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 275-287 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_21).

Full text not available from this repository.

Abstract

We consider weak Gabriel drawings of unbounded degree trees in the three-dimensional space. We assume a minimum distance between any two vertices. Under the same assumption, there exists an exponential area lower bound for general graphs. Moreover, all previously known algorithms to construct (weak) proximity drawings of trees, generally produce exponential area layouts, even when we restrict ourselves to binary trees. In this paper we describe a linear-time polynomial-volume algorithm that constructs a strictly-upward weak Gabriel drawing of any rooted tree with O(logn)-bit requirement. As a special case we describe a Gabriel drawing algorithm for binary trees which produces integer coordinates and n^3-area representations . Finally, we show that an infinite class of graphs requiring exponential area, admits linear-volume Gabriel drawings.The latter result can also be extended to \beta -drawings, for any 1< \beta <2, and relative neighborhood drawings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_21
Classifications:P Styles > P.840 Upward
G Algorithms and Complexity > G.070 Area / Edge Length
M Methods > M.900 Tree
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:313

Repository Staff Only: item control page

References

H. Alt, M. Godau, and S.H. Whitesides. Universal 3-dimensional visibility representations for graphs. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 8-19. Springer-Verlag, 1996.

G. Di Battista, W. Lenhart, and G. Liotta. Proximity drawability: a survey. In Graph Drawing (Proc. GD '94), vol. 894 of LNCS, Springer-Verlag, 1994.

G. Di Battista, G. Liotta, and S.H. Whitesides. The strength of weak proximity. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 178-189, Springer-Verlag, 1996.

P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity constraints and representable trees. In Graph Drawing (Proc. GD '94), vol. 894 of LNCS, Springer-Verlag, 1994.

P. Bose, W. Lenhart, and G. Liotta. Charakterizing proximity trees. Algoritmica, 16:83-110, 1996.

M. Brown and M. Najork. Algorithm animation usind 3D interactive graphics. In ACM Symp. on User Interface Software and Tech., pages 93-100, 1993.

T. Calamoneri and A. Sterbini. Drawing 2-,3-, and 4-colorable graphs in O(n²) volume. In [19], pp. 53-62.

M. Chrobak, M.T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319-328, 1996.

R.F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-dimensional graph drawing. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 1-11, 1995.

P. Eades and S.H. Whitesides. The realization problem for euclidian minimum spanning trees is np-hard. In Proc. ACM Symp. on Comp. Geom., 1994.

H. ElGindy, G. Liotta, A. Lubiw, H. Meijer, and S.H. Whitesides. Recognizing rectangle of influence drawable graphs. In R. Tamassia and I.G. Tollis, editors, Graph Drawing (Proc. GD '94), LNCS, 894, Springer-Verlag, pages 352-363, 1994.

K.R. Gabriel and R.R. Sokal. A new statistical approach to geographical analysis. Systematic Zoology. 18:54-64, 1969.

A. Garg and R. Tamassia. GIOTTO3D: A System for Visualizing Hierarchical Structures in 3D. In S.C. North, editor, Proceedings of Graph Drawing '96 (Proc. GD '96), vol. 1190 of LNCS, Springer-Verlag, 1997.

D.G. Kirkpatrick and J.D. Radke. A framework for computational morphology. In G.T. Toussaint, editor, Computational Geometry, pages 217-248. Elsevier, Amsterdam, 1985.

G. Liotta and G. Di Battista. Computing proximity drawings of trees in the 3-dimensional space. In Proc. 4th Workshop Algorithms and Data Structures, vol. 955 of LNCS, pp. 239-250. Springer-Verlag, 1995.

G. Liotta, R. Tamassia, I.G. Tollis, and P. Vocca. Area requirement of gabriel drawings. In Giancarlo Bongiovanni, Daniel Pier Bovet, and Giuseppe Di Battista, editors, Proc. CIAC '97, vol. 1203 of LNCS, pages 135-146, Springer-Verlag, 1997.

A. Lubiw and N. Sleumer. All maximal outerplanar graphs are relative neighborhood graphs. In Proc. 5th CCCG, pages 198-203, 1993.

G.G. Robertson, J.D. Mackinlay, and S.K. Card. Cone trees: Animated 3D-visualizations of hierarchical information. In Proc. CHI '91, pages 189-193.

D.W. Matula and R.R. Sokal. Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12(3):205-222, 1980.

M. Patrignani and F. Vargiu. 3DCube: A tool for three dimensional graph drawing. In [9], pp. 284-290.

J.D. Radke. On the shape of a set of points. In G.T. Toussaint, editor, Computational Morphology, pages 105-136, Amsterdam, The Netherlands, 1988. Northholland.

S. Reiss. An engine for the 3D visualization of program information. J. Visual Languages and Computing, 6(3), 1995.

G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:261-268, 1980.