|
TR-369-92
Layout of Rooted Trees |
|
| Authors: | Torocsik, Jeno, Pach, Joaanos |
| Date: | February 1992 |
| Pages: | 8 |
| Download Formats: | [PDF] |
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. |
|