[{"_id":"21781","article_type":"original","author":[{"last_name":"Dumitrescu","full_name":"Dumitrescu, Adrian","first_name":"Adrian"},{"first_name":"János","full_name":"Pach, János","last_name":"Pach"},{"id":"f86f7148-b140-11ec-9577-95435b8df824","full_name":"Saghafian, Morteza","first_name":"Morteza","last_name":"Saghafian"},{"last_name":"Scott","full_name":"Scott, Alex","first_name":"Alex"}],"doi":"10.2140/cnt.2026.15.73","quality_controlled":"1","OA_place":"repository","arxiv":1,"department":[{"_id":"HeEd"}],"scopus_import":"1","acknowledgement":"Research partially supported by ERC Advanced Grant \"GeoScape\", no. 882971 and\r\nHungarian NKFIH grant no. K-131529. Work by the third author is supported by EPSRC grant\r\nEP/X013642/1. Work by the third author is partially supported by the European Research Council (ERC), grant no. 788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","publication_status":"published","date_created":"2026-05-03T22:01:37Z","volume":15,"date_updated":"2026-05-07T07:45:24Z","oa":1,"ec_funded":1,"type":"journal_article","issue":"1","month":"04","publication":"Combinatorics and Number Theory","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","oa_version":"Preprint","date_published":"2026-04-17T00:00:00Z","page":"73-82","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2996-220X"],"issn":["2996-2196"]},"abstract":[{"text":"Given a set A of n points (vertices) in general position in the plane, the complete geometric graph \r\nKn[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.","lang":"eng"}],"publisher":"Mathematical Sciences Publishers","project":[{"name":"Alpha Shape Theory Extended","grant_number":"788183","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"Mathematics, Computer Science","grant_number":"Z00342","call_identifier":"FWF"}],"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2507.10840","open_access":"1"}],"article_processing_charge":"No","intvolume":"        15","citation":{"short":"A. Dumitrescu, J. Pach, M. Saghafian, A. Scott, Combinatorics and Number Theory 15 (2026) 73–82.","ieee":"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.","apa":"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>","mla":"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>.","ista":"Dumitrescu A, Pach J, Saghafian M, Scott A. 2026. Covering complete geometric graphs by monotone paths. Combinatorics and Number Theory. 15(1), 73–82.","ama":"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>","chicago":"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>."},"year":"2026","external_id":{"arxiv":["2507.10840"]},"day":"17","title":"Covering complete geometric graphs by monotone paths","OA_type":"green"}]