**Next:** Problem 46: 3D Minimum-Bend Orthogonal Graph Drawings

**Previous:** Problem 44: 3-Colorability of Arrangements of Great Circles

- Statement
How many points must be placed in the plane to support planar drawing of all planar graphs on n vertices? More precisely, call a set of points

*universal*if every planar graph on n vertices can be drawn with straight-line edges and without crossings by placing the vertices on a subset of the points. What is the smallest universal set of points as a function of n? In particular, is it O(n)?- Origin
Attributed to Mohar by János Pach (23 Nov. 2002). See also [CH89] for some of the history.

- Status/Conjectures
Open. Between \Theta(n) and \Theta(n^2).

- Partial and Related Results
By definition, a universal set of points must have size at least n. Chrobak and Karloff [CH89] proved the stronger result that any universal set of points must have at least 1.098n points.

On the other side, it is well-known that there are universal sets of points of size O(n^2). In particular, every planar graph can be drawn on the O(n) \times O(n) square grid [dFPP90], [Sch90]. However, any universal set of points forming a grid must have size at least n/3 \times n/3 [CH89].

Stephen Kobourov asks for the smallest value of n for which a universal point set of size n does not exist. He has checked by exhaustive search that there is a universal point set of size n for all n \leq 14.

It is now known that there is a universal set of n points if one bend per edge is permitted [ELLW10].

- Appearances
Posed by Stephen Koborouv during an open-problem session at the DIMACS Workshop on Computational Geometry (12th Annual Fall Workshop on Computational Geometry), Nov. 2002.

- Categories
graphs; point sets; graph drawing

- Entry Revision History
E. Demaine, 23 Nov. 2002; 20 Sep. 2003 (thanks to Sergio Cabello); J. O’Rourke, 29 Mar 2010 (thanks to Michael Hoffmann).

- [CH89]
M. Chrobak and H.Karloff. A lower bound on the size of universal sets for planar graphs.

*SIGACT News*, 20:83–86, 1989.- [ELLW10]
Hazel Everett, Sylvain Lazard, Giuseppe Liotta, and Stephen Wismath. Universal sets of n points for one-bend drawings of planar graphs with n vertices.

*Discr. Comput. Geom.*, 43(2):272–288, 2010.- [dFPP90]
H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid.

*Combinatorica*, 10(1):41–51, 1990.- [Sch90]
W. Schnyder. Embedding planar graphs on the grid. In

*Proc. 1st ACM-SIAM Sympos. Discrete Algorithms*, pages 138–148, 1990.