Crossing-free path cover lower bound cn

Problem 5.1 · arXiv:2507.10840

arXiv Problem high confidence— first stated 2026-01-10

Authors: Adrian Dumitrescu, János Pach, Morteza Saghafian, Alex Scott

Status open high confidence

Problem 5.1 asks whether there exists a constant c > 1/2 such that for infinitely many n there are n-element point sets A where every crossing-free-path covering of K_n[A] requires at least cn paths. The source paper proves that every complete convex geometric graph decomposes into n/2 + o(n) plane subgraphs (Pach–Saghafian–Schnider), establishing n/2 as a known threshold, but whether the crossing-free path covering number can exceed cn for c > 1/2 on general point sets remains open. No subsequent paper resolving this problem was found in a wide web search.

Reviewer notes. No follow-up resolving Problem 5.1 found. The concurrent paper arXiv:2507.06477 (An Improved Bound for Plane Covering Paths) addresses a different problem (covering point sets by plane paths, bound 6n/7) and does not cite or resolve Problem 5.1. The source paper itself provides quadratic lower bounds for monotone paths (requiring ≥ n²/15 monotone paths) but the open question concerns the linear regime for general crossing-free paths.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. Does there exist a constant $c>1/2$ with the property that, for infinitely many values of $n$, there are $n$-element point sets $A$ in the plane such that every covering of the edge set of $K_{n}[A]$ by crossing-free paths requires at least $cn$ paths?

Context

Pach, Saghafian, and Schnider proved that every complete convex geometric graph can be decomposed into $n/2 + o(n)$ plane subgraphs. It is open whether a linear lower bound strictly above $n/2$ holds for crossing-free path coverings over general point sets.

Source paper

Covering Complete Geometric Graphs by Monotone Paths
Adrian Dumitrescu, János Pach, Morteza Saghafian, Alex Scott · 2026-01-10
https://arxiv.org/abs/2507.10840