pith. sign in

arxiv: 1104.1307 · v8 · pith:PXQQY7VZnew · submitted 2011-04-07 · 💻 cs.DM

On Sets of Lines Not-Supporting Trees

classification 💻 cs.DM
keywords linesiotamathcaltreesaskedbijectiondujmovicembedding
0
0 comments X
read the original 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 \rightarrow \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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.