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

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); E. Demaine, 7 Dec 2012 (thanks to Jean Cardinal and Vincent Kusters).

Bibliography

CHK12

Jean Cardinal, Michael Hoffmann, and Vincent Kusters.
On universal point sets for planar graphs.
arXiv:1209.3594, September 2012.
Presented at TJJCCGG 2012.

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., 3(2):??-??, 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.