Caterpillars and alternating paths

Let $p(m)$ (respectively, $q(m)$) be the maximum number $k$ such that any tree with $m$ edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with $k$ edges. We derive closed-form expressions for $p(m)$ and $q(m)$ for all $m ge 1$. The two functions $p(n)$ and $q(n)$ can also be interpreted in terms of alternating paths among $n$ disjoint line segments in the plane, whose $2n$ endpoints are in convex position.

Disjoint axis-parallel segments without a circumscribing polygon

We construct a family of 17 disjoint axis-parallel line segments in the plane that do not admit a circumscribing polygon.

Linking disjoint axis-parallel segments into a simple polygon is hard too

Deciding whether a family of disjoint axis-parallel line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.

Moving intervals for packing and covering

We study several problems on geometric packing and covering with movement. Given a family $mathcal{I}$ of $n$ intervals of $kappa$ distinct lengths, and another interval $B$, can we pack the intervals in $mathcal{I}$ inside $B$ (respectively, cover $B$ by the intervals in $mathcal{I}$) by moving $tau$ intervals and keeping the other $sigma = n - tau$ intervals unmoved? We show that both packing and covering are W[1]-hard with any one of $kappa$, $tau$, and $sigma$ as single parameter, but are FPT with combined parameters $kappa$ and $tau$. We also obtain improved polynomial-time algorithms for packing and covering, including an $O(nlog^2 n)$ time algorithm for covering, when all intervals in $mathcal{I}$ have the same length.

Linking disjoint segments into a simple polygon is hard

Deciding whether a family of disjoint line segments in the plane can be linked into a simple polygon (or a simple polygonal chain) by adding segments between their endpoints is NP-hard.

On universal covers for carpenters rule folding

We present improved universal covers for carpenters rule folding in the plane.