Smallest universal point sets for planar graphs

How many points must be placed in the plane so that every planar graph with $n$ vertices can be drawn with straight, non-crossing edges using some of those points as vertices? About $n^2/4$ points are known to suffice and about $1.3n$ are necessary; whether a linear number suffices is a well-known open question in graph drawing.

Problem

A finite set $U\subset\mathbb{R}^2$ is $n$-universal if every planar graph with $n$ vertices has a plane straight-line drawing whose vertices are distinct points of $U$. Let $f(n)$ be the smallest size of an $n$-universal set. Since every planar graph is a subgraph of a maximal planar graph (a triangulation), it is enough to draw all triangulations on $n$ vertices.

Question. Is $f(n)=O(n)$? More generally, determine the growth of $f(n)$.

Background

The question is attributed to Bojan Mohar; Stephen Kobourov presented it at an open-problem session of the 2002 DIMACS Fall Workshop on Computational Geometry and also asked for the smallest $n$ with $f(n)>n$. Universal point sets matter in graph drawing because they let a single fixed set of positions, such as a screen grid, serve every graph of a given size. The problem links to permutation patterns: Bannister, Cheng, Devanny and Eppstein showed that superpatterns for 213-avoiding permutations give universal point sets [3].

What is known

• Upper bounds. Every planar graph on $n$ vertices can be drawn on a grid of size $O(n)\times O(n)$ (de Fraysseix, Pach and Pollack [5]; Schnyder, both 1990), so $f(n)=O(n^2)$. Bannister, Cheng, Devanny and Eppstein (2014) reduced this to $n^2/4-\Theta(n)$ [3], the best refereed bound.
• A recent claim. A September 2026 preprint by T. Gordon claims $f(n)\le n\,e^{O(\sqrt{\log n})}=n^{1+o(1)}$, by constructing superpatterns for 213-avoiding permutations of that length and applying the reduction of [3] [6]. It is an unrefereed preprint. The author's Lean formalization covers an earlier superpattern construction with the same $n^{1+o(1)}$ bound, but not the reduction to point sets. Even if correct, it leaves $f(n)=O(n)$ open.
• Lower bounds. $f(n)\ge 1.098n$ (Chrobak and Karloff, 1989) [1], improved to $1.235n$ (Kurowski, 2004) and to $(1.293-o(1))n$ (Scheucher, Schrezenmaier and Steiner, 2020) [2].
• Small cases. Universal sets of exactly $n$ points exist for every $n\le 10$ but not for $n\ge 15$ (Cardinal, Hoffmann and Kusters, 2015) [4], and an exhaustive search showed that none exists for $n=11$ [2].
• Relaxations. If each edge may bend once, $n$ points suffice (Everett, Lazard, Liotta and Wismath, 2010).

What would count as progress

• An explicit $n$-universal set for a specific $n$ with fewer points than previously known, given with exact coordinates and a straight-line drawing of every triangulation on $n$ vertices, so that a program can check it.
• A lower bound $f(n)\ge cn$ with $c>1.293$, or a superlinear lower bound.
• An independent check of the $n^{1+o(1)}$ construction (or a flaw in it), or a construction of linear size.

References

1. M. Chrobak and H. Karloff, A lower bound on the size of universal sets for planar graphs, ACM SIGACT News 20(4) (1989), 83–86. doi:10.1145/74074.74088
2. M. Scheucher, H. Schrezenmaier and R. Steiner, A note on universal point sets for planar graphs, J. Graph Algorithms Appl. 24 (2020), 247–267. doi:10.7155/jgaa.00529
3. M. J. Bannister, Z. Cheng, W. E. Devanny and D. Eppstein, Superpatterns and universal point sets, J. Graph Algorithms Appl. 18 (2014), 177–209. doi:10.7155/jgaa.00318
4. J. Cardinal, M. Hoffmann and V. Kusters, On universal point sets for planar graphs, J. Graph Algorithms Appl. 19 (2015), 529–547. doi:10.7155/jgaa.00374
5. H. de Fraysseix, J. Pach and R. Pollack, How to draw a planar graph on a grid, Combinatorica 10 (1990), 41–51. doi:10.1007/BF02122694
6. T. Gordon, Almost linear universal point sets for planar graphs, preprint (2026). arXiv:2609.10916

Source

Imported from The Open Problems Project, Problem 45, curated by Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.