The Minimum Number of Plane Graphs for Sets with Small Hulls
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.29446
curl -X POST /api/v1/records/arxiv/2606.29446/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.29446/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'