Covering Complete Geometric Graphs by Monotone Paths
arXiv preprint arXiv:2507.10840, 2025•arxiv.org
Given a set $ A $ of $ n $ points (vertices) in general position in the plane, the\emph
{complete geometric graph} $ K_n [A] $ consists of all $\binom {n}{2} $ segments (edges)
between the elements of $ A $. It is known that the edge set of every complete geometric
graph on $ n $ vertices can be partitioned into $ O (n^{3/2}) $ crossing-free paths (or
matchings). We strengthen this result under various additional assumptions on the point set.
In particular, we prove that for a set $ A $ of $ n $\emph {randomly} selected points, uniformly …
{complete geometric graph} $ K_n [A] $ consists of all $\binom {n}{2} $ segments (edges)
between the elements of $ A $. It is known that the edge set of every complete geometric
graph on $ n $ vertices can be partitioned into $ O (n^{3/2}) $ crossing-free paths (or
matchings). We strengthen this result under various additional assumptions on the point set.
In particular, we prove that for a set $ A $ of $ n $\emph {randomly} selected points, uniformly …
Given a set of points (vertices) in general position in the plane, the \emph{complete geometric graph} consists of all segments (edges) between the elements of . It is known that the edge set of every complete geometric graph on vertices can be partitioned into crossing-free paths (or matchings). We strengthen this result under various additional assumptions on the point set. In particular, we prove that for a set of \emph{randomly} selected points, uniformly distributed in , with probability tending to as , the edge set of can be covered by crossing-free paths and by crossing-free matchings. On the other hand, we construct -element point sets such that covering the edge set of requires a quadratic number of monotone paths.
arxiv.org