Jan Kratochvíl

collaborators

2 papers

cs.CG2026

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

Todor AntiÄ, JiÅÃ Fiala, Jelena GliÅ¡iÄ +8

Let $I^$ be a straight-line crossing-free drawing of a tree $T$ . A \emph{bad pair} in $I^$ is a pair of non-adjacent vertices of $T$ whose Euclidean distance in $I^$ is smaller tha…

cs.CG2025

Three Edge-disjoint Plane Spanning Paths in a Point Set

Philipp Kindermann, Jan KratochvÃl, Giuseppe Liotta +1

We consider the following problem: Given a set $S$ of $n$ distinct points in the plane, how many edge-disjoint plane straight-line spanning paths can be drawn on $S$ ? Each spanning…