{"id":"arxiv/2607.20007","url":"https://arxiv.org/abs/2607.20007","tags":["cs.CG","cs.DM","math.CO"],"score":0,"title":"How Close is a Tree to a Euclidean Minimum Spanning Tree?","domain":"cs.CG","source":"arxiv","authors":["Todor Antić","Jiří Fiala","Jelena Glišić","Grzegorz Gutowski","Konstanty Junosza-Szaniawski","Jan Kratochvíl","Giuseppe Liotta","Morteza Saghafian","Maria Saumell","Krisztina Szilágyi","Pavel Valtr"],"reviews":0,"subject":"cs.CG","summary":"Let $Γ$ be a straight-line crossing-free drawing of a tree $T$. A \\emph{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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-22","reactions":{}}