Genus approximation hardness in spherical density regime
Open Problem (Spherical Density Regime) · arXiv:2011.08049
Status open high confidence
No resolution of the spherical density regime open problem has been found in the literature. The source paper (published in J. ACM 71(6), 2024) identifies the genus approximation problem for graphs with average degree at most 6 as the major open problem in its density-regime framework; Conjecture 1.1 of the paper (APX-hardness for cubic graphs) is the authors' leading candidate resolution but remains unproved. A wide search across arXiv, Jing's research page, and general queries on genus approximation hardness returned no follow-up paper addressing either the spherical regime or the APX-hardness conjecture for cubic graphs.
Reviewer notes. The open problem has two possible resolutions: (a) an efficient constant-factor approximation algorithm for genus in the spherical density regime (average degree ≤ 6), or (b) a proof that approximation is hard in this regime. Conjecture 1.1 of the paper conjectures APX-hardness for cubic graphs as the most likely resolution; this conjecture itself remains open. No follow-up found in indexed literature as of 2026-05-14.
Context
The authors partition the genus approximation problem into three density regimes. The spherical density regime (average degree $\leq 6$) is described as 'probably most interesting'; no efficient constant-factor approximation algorithm is known for it, and the authors identify resolving this as 'the major open problem'. Conjecture 1.1 (APX-hardness for cubic graphs) is the leading candidate resolution.
Notes. Stated in prose: 'resolving this is the major open problem'; no formal labelled theorem environment.
Source paper
Efficient polynomial-time approximation scheme for the genus of dense graphs
Yifan Jing, Bojan Mohar · 2024-08-27
https://arxiv.org/abs/2011.08049