Covering complete geometric graphs by monotone paths Dumitrescu, Adrian Pach, János Saghafian, Morteza Scott, Alex 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. Mathematical Sciences Publishers 2026 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/21781 Dumitrescu A, Pach J, Saghafian M, Scott A. Covering complete geometric graphs by monotone paths. <i>Combinatorics and Number Theory</i>. 2026;15(1):73-82. doi:<a href="https://doi.org/10.2140/cnt.2026.15.73">10.2140/cnt.2026.15.73</a> eng info:eu-repo/semantics/altIdentifier/doi/10.2140/cnt.2026.15.73 info:eu-repo/semantics/altIdentifier/issn/2996-2196 info:eu-repo/semantics/altIdentifier/e-issn/2996-220X info:eu-repo/semantics/altIdentifier/arxiv/2507.10840 info:eu-repo/semantics/openAccess