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 , pp. 275-287(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item