Layout of Rooted Trees
Report ID: TR-369-92Author: Pach, Joaanos / Torocsik, Jeno
Date: 1992-02-00
Pages: 8
Download Formats: |PDF|
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.