k-planar partition bound tightness for convex sets
Question 9 · arXiv:2112.08456
Status open high confidence
Question 9 asks whether the gap between the upper bound of approximately n/sqrt(2k) and the lower bound of approximately (n-1)/(4.93*sqrt(k)) on the number of k-planar subgraphs needed to partition K(P) for a convex n-point set is tight up to lower-order terms. No follow-up paper addressing the tightness of these bounds was found after an exhaustive search of the literature through May 2026. The paper was published at SoCG 2022; subsequent related work (GD 2024, arXiv:2405.17172) addresses plane (k=0) partitions on dense point sets, not the k-planar tightness question.
Reviewer notes. No follow-up work closing the constant-factor gap between O(n/sqrt(k)) upper bound and Omega(n/sqrt(k)) lower bound was found. The paper notes that for k=2 a lower bound of 3n/10 nearly matching the upper bound n/3 can be shown, but this specialised case does not settle the general question. The conjecture is open with high confidence as of May 2026.
Context
Theorem 2 shows that for a convex $n$-point set $P$ and every $k \in \mathbb{N}$, $K(P)$ admits a partition into at most $\frac{n}{\sqrt{2k}}$ $k$-planar subgraphs (for appropriate $s$), while at least $\frac{n-1}{4.93\sqrt{k}}$ subgraphs are required. Question 9 asks whether these bounds match up to lower-order terms. The authors note that for $k=2$ they can show a lower bound of $\frac{3n}{10}$ almost matching the upper bound $\frac{n}{3}$, but omit this from the current version.
Source paper
Edge Partitions of Complete Geometric Graphs (Part 2)
Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, Birgit Vogtenhuber · 2021-12-15
https://arxiv.org/abs/2112.08456
PDF source