Universal point sets for planar graphs
We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.
More generally, if we let denote the size of the smallest -universal set, we are interested in the behaviour of . The best known upper bound is . Indeed, every -vertex planar graph can be drawn as required in the grid [dFPP], [S]. On the flip side, it is known that for sufficiently large [CH].
[CH] M. Chrobak and H.Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20:83-86, 1989.
[S] W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.
* indicates original appearance(s) of problem.