Problem 45: Smallest Universal Set of Points for Planar Graphs

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²).

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²). 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. He has checked by exhaustive search that there is a universal point set of size n for all n $\leq$ 14.

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).

Bibliography

CH89

M. Chrobak and H.Karloff.
A lower bound on the size of universal sets for planar graphs.
SIGACT News, 20:83-86, 1989.

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.