On Sets of Lines Not-Supporting Trees

Abstract

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 $\iota :V\to \mathcal{L}$, we are asked to find a crossing-free straight-line embedding of $T$ so that $v\in \iota (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 $\iota$ 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.

a revised version, a correction of the abstract

References in corpus (1)

• A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing