Universal point set
In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.
When n is ten or less, there exist universal point sets with exactly n points, but for all n ≥ 15 additional points are required.
Several authors have shown that subsets of the integer lattice of size O(n) × O(n) are universal. In particular, de Fraysseix, Pach & Pollack (1988) showed that a grid of (2n − 3) × (n − 1) points is universal, and Schnyder (1990) reduced this to a triangular subset of an (n − 1) × (n − 1) grid, with n2/2 − O(n) points. By modifying the method of de Fraysseix et al., Brandenburg (2008) found an embedding of any planar graph into a triangular subset of the grid consisting of 4n2/9 points. A universal point set in the form of a rectangular grid must have size at least n/3 × n/3 but this does not rule out the possibility of smaller universal point sets of other types. The smallest known universal point sets are not based on grids, but are instead constructed from superpatterns (permutations that contain all permutation patterns of a given size); the universal point sets constructed in this way have size n2/4 − O(n).
de Fraysseix, Pach & Pollack (1988) proved the first nontrivial lower bound on the size of a universal point set, with a bound of the form n + Ω(√n), and Chrobak & Karloff (1989) showed that universal point sets must contain at least 1.098n − o(n) points. Kurowski (2004) stated an even stronger bound of 1.235n − o(n), which remains the best lower bound known.
Closing the gap between the known linear lower bounds and quadratic upper bounds remains an open problem.
...
Wikipedia