Asymptotic maximal plane-saturation ratio conjecture

For a maximal planar graph GG on nn vertices, let its plane-saturation ratio be the relevant ratio measuring the size of a largest plane-saturated subgraph relative to GG. Plane-saturation ratio conjecture. If nn tends to infinity, the maximum value of the plane-saturation ratio over the set of maximal planar graphs GG on nn vertices tends to

12.\frac{1}{2}.

The paper establishes a lower bound for this maximum but states that asymptotic optimality of the lower bound is only suspected, so the limiting value remains open.

Sources & referencesView supporting material

Primary source

Alexander Clifton and Dániel G. Simon, “Saturated Partial Embeddings of Maximal Planar Graphs”, arXiv:2412.06068 (2024).

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.