On Sets of Lines Not-Supporting Trees
Radoslav Fulek, Daniel Neuwirth · arXiv (Cornell University) · 2011
We study the following problem introduced by Dujmovic et al. Given a tree $T = (V,E)$, on $n$ vertices, a set of $n$ lines $\mathcal{L}$ in the plane and a bijection $ι: V \rightarrow \mathcal{L}$, we are asked to find a crossing-free straight-line embedding of $T$ so that $v\in ι(v)$, for all $v\in V$. We say that a set of $n$ lines $\mathcal{L}$ is universal for trees if for any tree $T$ and any bijection $ι$ there exists such an embedding. We prove that any sufficiently big set of lines is not universal for trees, which solves an open problem asked by Dujmovic et al.