@misc{gdea_3830,
          editor = {Seok-Hee Hong and Takao Nishizeki and Wu Quan},
           title = {Straight-Line Orthogonal Drawings of Binary and Ternary Trees},
          author = {Fabrizio Frati},
       publisher = {Springer},
            year = {2008},
           pages = {76--87},
             url = {http://gdea.informatik.uni-koeln.de/830/},
        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.
}
}