Id: arxiv/2606.29446 Url: https://arxiv.org/abs/2606.29446 Tags: math.CO Score: 0 Title: The Minimum Number of Plane Graphs for Sets with Small Hulls Domain: math.CO Source: arxiv Authors: Alice Chen, Tara Saini, Adam Sheffer, Angela Zhang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-28 Page: https://delphi.science/r/arxiv/2606.29446 Let $\mathcal{P}$ be a set of $n$ points in $\mathbb{R}^2$, with a convex hull of size $O(n/\log n)$. We prove that $Ω(12.24^n)$ plane graphs can be drawn on $\mathcal{P}$, the first non-trivial bound for this problem. We also show that a random plane graph, uniformly chosen from the set of all plane graphs of $\mathcal{P}$, has at most $n/12.24$ isolated vertices. This improves upon a previous bound of $n/10.18$. Our analysis is based on studying the expected vertex potentials in a random plane graph. The potential of a vertex is its degree plus the number of vertices visible from it. We…