Asymptotic maximal plane-saturation ratio conjecture

About 2 years old · traced to

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.

References

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.