Layout of Rooted Trees

Abstract:

Let $S$ be a set of $n$ points in the plane in general position. The
depth of a point $p(mo S$ is the minimum number of elements of $S$ in
a closed halfplane containing $p$. We prove that, if $p$ is not the
deepest point of $S$ or the depth of $p$ is at most $n over 3$ $+1$,
then any tree with $n$ vertices and with root $r$ can be straight-line
embedded on $S$ so that $r$ is mapped onto $p.$ This gives a partial
answer to a problem raised by Micha Perles.