Smallest universal point sets for planar graphs
A set $U$ of points in the plane is universal for $n$ if every planar graph on $n$ vertices has a crossing-free straight-line drawing with all its vertices at points of $U$.
A universal set has at least $n$ points, and Chrobak and Karloff raised this lower bound to $1.098n$. Since every planar graph can be drawn on an $O(n)\times O(n)$ grid (de Fraysseix, Pach and Pollack; Schnyder), $O(n^2)$ points suffice, while Chrobak and Karloff showed that a universal set in the form of a grid needs at least $n/3 \times n/3$ points. Kobourov, asking for the least $n$ with no universal set of exactly $n$ points, found by exhaustive search that such sets exist for all $n \le 14$. If each edge may bend once, Everett, Lazard, Liotta and Wismath found universal sets of $n$ points.
Problem. Determine, in terms of $n$, the minimum number of points in a universal set for $n$. In particular, do $O(n)$ points suffice?
Source: Attributed to Mohar by Pach (2002); see Chrobak and Karloff (1989) for history; posed by Kobourov at the 12th Annual Fall Workshop on Computational Geometry (DIMACS, 2002); Problem 45 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG
- Keywords
- straight-line drawings of planar graphs, The Open Problems Project, universal point sets
References
@article{chrobak1989,
author = {Chrobak, M. and Karloff, H.},
title = {A Lower Bound on the Size of Universal Sets for Planar Graphs},
journal = {SIGACT News},
volume = {20},
number = {4},
year = {1989},
pages = {83--86},
url = {http://www.cs.ucr.edu/~marek/pubs/univ_sets_low_bound.ps}
}
@article{defraysseix1990,
author = {de Fraysseix, H. and Pach, J. and Pollack, R.},
title = {How to Draw a Planar Graph on a Grid},
journal = {Combinatorica},
volume = {10},
number = {1},
year = {1990},
pages = {41--51}
}
@inproceedings{schnyder1990,
author = {Schnyder, W.},
title = {Embedding Planar Graphs on the Grid},
booktitle = {Proc. 1st ACM-SIAM Sympos. Discrete Algorithms},
year = {1990},
pages = {138--148}
}
@article{everett2010,
author = {Everett, Hazel and Lazard, Sylvain and Liotta, Giuseppe and Wismath, Stephen},
title = {Universal Sets of $n$ Points for One-bend Drawings of Planar Graphs with $n$ Vertices},
journal = {Discr. Comput. Geom.},
volume = {43},
number = {2},
year = {2010},
pages = {272--288}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01091, "Smallest universal point sets for planar graphs", clopen.solutions.