On the other side, it is well-known that there are universal sets of points of size O(n2). In particular, every planar graph can be drawn on the O(n)×O(n) square grid [dFPP90,Sch90]. However, any universal set of points forming a grid must have size at least n/3×n/3 [CH89].
Stephen Kobourov asks for the smallest value of n for which a universal point set of size n does not exist. Cardinal, Hoffmann, and Kusters [CHK12] proved that no n≥15 has a universal point set of size n. Furthermore, they have verified that every n≤10 has a universal point set of size n. (An earlier version of this page claimed that every n≤14 has a universal point set, which would completely settle Koborouv's question, but this claim appears unsubstantiated.)
It is now known that there is a universal set of n points if one bend per edge is permitted [ELLW10].