How Close is a Tree to a Euclidean Minimum Spanning Tree?

Let $\Gamma$ be a straight-line crossing-free drawing of a tree $T$.

A \emph{bad pair} in $\Gamma$ is a pair of non-adjacent vertices of $T$ whose Euclidean distance in $\Gamma$ is smaller than the length of the longest edge in the path connecting them in~$\Gamma$.

When $\Gamma$ has no bad pairs, $\Gamma$ is a Euclidean Minimum Spanning Tree of its vertex set (or EMST-drawing for short).

Deciding whether a tree of maximum degree at most six admits an EMST-drawing is known to be \NP-hard.

In contrast, we characterize those caterpillars that admit an EMST-drawing.

The characterization gives rise to a linear-time algorithm that decides if a caterpillar admits an EMST-drawing, and in the affirmative case, computes such a drawing.

For caterpillars of maximum degree six, we further present a linear-time algorithm to compute a crossing-free straight-line drawing with the minimum number of bad pairs.

For $n$-vertex trees with maximum vertex degree $\Delta$, we prove the $\Delta^2n\log n$ upper bound on the minimum number of bad pairs.

In the special case of stars, we construct a drawing with the minimum number of bad pairs.