2026/07/22 by Todor Antić, Jiří Fiala, Jelena Glišić +8
#cs.CG #cs.DM #math.CO
Let Γ be a straight-line crossing-free drawing of a tree T. A bad pair in Γ is a pair of non-adjacent vertices of T whose Euclidean distance in Γ is smaller than the length of the longest edge in the path connecting them in~Γ. When Γ has no bad pairs, Γ 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 Δ, we prove the Δ2nlog 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.