Covering complete geometric graphs by monotone paths

Journal article

Given a set $A$ of $n$ points (vertices) in general position in the plane, the 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$ randomly selected points, uniformly distributed in $[0,1]^2$, with probability tending to 1 as $n \to \infty$, the edge set of $K_n[A]$ can be covered by $O(n \log n)$ crossing-free paths and by $O(n \sqrt{\log n})$ crossing-free matchings. On the other hand, we construct $n$-element point sets such that covering the edge set of $K_n(A)$ requires a quadratic number of monotone paths.

Authors: Dumitrescu, A; Pach, J; Saghafian, M; Scott, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Mathematical Sciences Publishers
• Journal: Combinatorics and Number Theory
• Volume: 15
• Issue: 1
• Pages: 73–82
• Publication date: 2026-04-17
• Acceptance date: 2026-03-23
• DOI: 10.2140/cnt.2026.15.73
• EISSN: 2996-220X
• ISSN: 2996-2196
• Language: English
• Keywords: plane subgraph; convexity; geometric graph; complete graph; crossing family