Universal point set

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.

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 − Θ(n).

Less obviously, every set of n points in general position (no three collinear) remains universal for outerplanar graphs.

[7] Planar 3-trees have universal point sets of size O(n3/2 log n); the same bound also applies to series–parallel graphs.

[9] By using a similar layout, every strictly convex curve in the plane can be shown to contain an n-point subset that is universal for polyline drawing with at most one bend per edge.

Grid drawing of a nested triangles graph . In any drawing of this graph, at least half of the triangles must form a nested chain, which requires a bounding box of size at least n /3 × n /3. The layout shown here comes close to this, using size approximately n /3 × n /2
An arc diagram