next up previous
Next: Problem 46: 3D Minimum-Bend Up: The Open Problems Project Previous: Problem 44: 3-Colorability of


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 Θ(n2).
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(n2). In particular, every planar graph can be drawn on the O(nO(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.


next up previous
Next: Problem 46: 3D Minimum-Bend Up: The Open Problems Project Previous: Problem 44: 3-Colorability of
The Open Problems Project - December 08, 2012