@article{21781,
  abstract     = {Given a set A of n points (vertices) in general position in the plane, the complete geometric graph 
Kn[A] consists of all (n2) 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(n3∕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→∞, the edge set of Kn[A] can be covered by O(nlogn) crossing-free paths and by O(n√logn) crossing-free matchings. On the other hand, we construct n-element point sets such that covering the edge set of Kn[A] requires a quadratic number of monotone paths.},
  author       = {Dumitrescu, Adrian and Pach, János and Saghafian, Morteza and Scott, Alex},
  issn         = {2996-220X},
  journal      = {Combinatorics and Number Theory},
  number       = {1},
  pages        = {73--82},
  publisher    = {Mathematical Sciences Publishers},
  title        = {{Covering complete geometric graphs by monotone paths}},
  doi          = {10.2140/cnt.2026.15.73},
  volume       = {15},
  year         = {2026},
}