---
OA_place: repository
OA_type: green
_id: '21781'
abstract:
- lang: eng
  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."
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."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Adrian
  full_name: Dumitrescu, Adrian
  last_name: Dumitrescu
- first_name: János
  full_name: Pach, János
  last_name: Pach
- first_name: Morteza
  full_name: Saghafian, Morteza
  id: f86f7148-b140-11ec-9577-95435b8df824
  last_name: Saghafian
- first_name: Alex
  full_name: Scott, Alex
  last_name: Scott
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: A. Dumitrescu, J. Pach, M. Saghafian, A. Scott, Combinatorics and Number
    Theory 15 (2026) 73–82.
date_created: 2026-05-03T22:01:37Z
date_published: 2026-04-17T00:00:00Z
date_updated: 2026-05-07T07:45:24Z
day: '17'
department:
- _id: HeEd
doi: 10.2140/cnt.2026.15.73
ec_funded: 1
external_id:
  arxiv:
  - '2507.10840'
intvolume: '        15'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2507.10840
month: '04'
oa: 1
oa_version: Preprint
page: 73-82
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '788183'
  name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: Mathematics, Computer Science
publication: Combinatorics and Number Theory
publication_identifier:
  eissn:
  - 2996-220X
  issn:
  - 2996-2196
publication_status: published
publisher: Mathematical Sciences Publishers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Covering complete geometric graphs by monotone paths
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2026'
...