article published yes Adrian Dumitrescu author János Pach author Morteza Saghafian author f86f7148-b140-11ec-9577-95435b8df824 Alex Scott author HeEd department Alpha Shape Theory Extended project Mathematics, Computer Science project 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 Publishers2026 eng 2996-2196 2996-220X 2507.1084010.2140/cnt.2026.15.73 15173-82 A. Dumitrescu, J. Pach, M. Saghafian, and A. Scott, “Covering complete geometric graphs by monotone paths,” <i>Combinatorics and Number Theory</i>, vol. 15, no. 1. Mathematical Sciences Publishers, pp. 73–82, 2026. 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> Dumitrescu, Adrian, János Pach, Morteza Saghafian, and Alex Scott. “Covering Complete Geometric Graphs by Monotone Paths.” <i>Combinatorics and Number Theory</i>. Mathematical Sciences Publishers, 2026. <a href="https://doi.org/10.2140/cnt.2026.15.73">https://doi.org/10.2140/cnt.2026.15.73</a>. Dumitrescu, A., Pach, J., Saghafian, M., &#38; Scott, A. (2026). Covering complete geometric graphs by monotone paths. <i>Combinatorics and Number Theory</i>. Mathematical Sciences Publishers. <a href="https://doi.org/10.2140/cnt.2026.15.73">https://doi.org/10.2140/cnt.2026.15.73</a> Dumitrescu A, Pach J, Saghafian M, Scott A. 2026. Covering complete geometric graphs by monotone paths. Combinatorics and Number Theory. 15(1), 73–82. A. Dumitrescu, J. Pach, M. Saghafian, A. Scott, Combinatorics and Number Theory 15 (2026) 73–82. Dumitrescu, Adrian, et al. “Covering Complete Geometric Graphs by Monotone Paths.” <i>Combinatorics and Number Theory</i>, vol. 15, no. 1, Mathematical Sciences Publishers, 2026, pp. 73–82, doi:<a href="https://doi.org/10.2140/cnt.2026.15.73">10.2140/cnt.2026.15.73</a>. 217812026-05-03T22:01:37Z2026-05-07T07:45:24Z