Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

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