Proximity drawings of binary trees in polynomial area.
Paolo Penna, Paola Vocca · 1998
In this paper, we study weak β-proximity drawings. All known algorithms that compute (weak) proximity drawings produce representations whose area increases exponentially with the number of vertices. Additionally, an exponential lower bound on the area of (weak) proximity drawings of general graph has been proved. We present the first algorithms that compute a polynomial area β-proximity drawing of binary and ternary trees. The algorithms run in linear time.