{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-28","reactions":{}}