Next: Problem 46: 3D Minimum-Bend Orthogonal Graph Drawings
Previous: Problem 44: 3-Colorability of Arrangements of Great Circles
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)?
Attributed to Mohar by János Pach (23 Nov. 2002). See also [CH89] for some of the history.
Open. Between \Theta(n) and \Theta(n^2).
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].
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.
graphs; point sets; graph drawing
E. Demaine, 23 Nov. 2002; 20 Sep. 2003 (thanks to Sergio Cabello); J. O’Rourke, 29 Mar 2010 (thanks to Michael Hoffmann).
M. Chrobak and H.Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20:83–86, 1989.
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.
H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990.
W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138–148, 1990.