Minimum zig-zag path cover of complete geometric graphs
Problem 5.2 · arXiv:2507.10840
Status open high confidence
Problem 5.2 asks for the smallest z=z(n) such that every complete geometric graph on n vertices can be covered by z plane zig-zag paths. The source paper (arXiv:2507.10840) proves that for any finite point set in general position, the edge set can be covered by plane Hamiltonian zig-zag paths, establishing that z(n) is finite, but the exact asymptotics remain unknown. No follow-up work resolving this problem was found in a wide web search conducted in May 2026.
Reviewer notes. No follow-up found. The paper proves existence of a covering by plane Hamiltonian zig-zag paths (upper bound on z(n)), but neither upper nor lower bounds on z(n) are established. The paper is recent (arXiv submission July 2025, published January 2026) and the problem is newly posed, making the absence of follow-up expected.
Context
The authors show that for any finite point set $A$ in general position in the plane, one can cover the edge set of $K_n[A]$ by plane Hamiltonian zig-zag paths, but the minimum number of such paths needed in the worst case is left open.
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