Hudák–Madaras–Suzuki conjecture on 3-connected maximal 1-planar graph size

Let P\overline{\mathcal{P}^\star} be the family of 3-connected maximal 1-planar graphs, and let m(P,n)m(\overline{\mathcal{P}^\star},n) denote the minimum number of edges among graphs in this family with nn vertices. Hudák–Madaras–Suzuki conjecture.

m(P,n)=185n+c,m(\overline{\mathcal{P}^\star},n)=\frac{18}{5}n+c,

where cc is a constant. The paper states that its results disprove the related conjecture that every 3-connected maximal 1-planar graph has at least 185n+O(1)\frac{18}{5}n+O(1) edges.

Sources & referencesView supporting material

Primary source

Zhangdong Ouyang, Yuanqiu Huang, Licheng Zhang and Fengming Dong, “The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity”, arXiv:2504.21558 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.