Straight-Line Orthogonal Drawings of Binary and Ternary Trees

Frati, Fabrizio (2008) Straight-Line Orthogonal Drawings of Binary and Ternary Trees. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 76-87(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_11).

Full text not available from this repository.

Abstract

In this paper we provide upper and lower bounds on the area requirement of straight-line orthogonal drawings of $n$-node binary and ternary trees. Namely, we show algorithms for constructing order-preserving straight-line orthogonal drawings of binary trees in $O(n^1.5)$ area, straight-line orthogonal drawings of ternary trees in $O(n^1.631)$ area, and straight-line orthogonal drawings of complete ternary trees in $O(n^1.262)$ area. As far as we know, the ones we present are the first algorithms achieving sub-quadratic area for these problems. Further, for upward order-preserving straight-line orthogonal drawings of binary trees and for order-preserving straight-line orthogonal drawings of ternary trees we provide $Omega(n^2)$ area lower bounds, that we also prove to be tight.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_11
Classifications: P Styles > P.600 Poly-line > P.600.700 Orthogonal
M Methods > M.900 Tree
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/830

Actions (login required)

View Item View Item