PreprintarXiv licencearXiv
Almost Linear Universal Point Sets for Planar Graphs
Abstract
A point set is universal for planar graphs on n vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size n1+o(1), improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.
Related
- Large Planar Point Sets Contain 4 Collinear Points or Almost 7-Cliques, and Related Results
- Almost Empty Monochromatic Polygons in Planar Point Sets
- Four-Coloring Planar Graphs in Linear Time
- Almost Every Graph Is Reconstructible from Its Token Graphs
- Precise universal edge asymptotics for planar β=2 Coulomb gases with radial external fields
BibTeX
@misc{gordon2026almost,
title = {{Almost Linear Universal Point Sets for Planar Graphs}},
author = {Taylor Gordon},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10916},
eprint = {2609.10916},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10916},
}
RIS
TY - UNPB
TI - Almost Linear Universal Point Sets for Planar Graphs
AU - Taylor Gordon
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.10916
UR - https://arxiv.org/abs/2609.10916
AB - A point set is universal for planar graphs on n vertices if every such graph has a straight-line drawing without crossings whose vertices belong to the set. We construct universal point sets of size n^1+o(1), improving the previous quadratic upper bound. Our construction uses the reduction of Bannister, Cheng, Devanny, and Eppstein from universal point sets to superpatterns for $213$-avoiding permutations. We represent these permutations by ordered rooted forests and construct a small family of intervals containing every such forest. The result follows from a straightforward bound on the size of the family of intervals. GPT-6 Astra assisted in developing the construction and proof.
ER -