Universal point sets for planar graphs
Status partial high confidence
The question of whether an $n$-universal set of size $O(n)$ exists for all $n$-vertex planar graphs remains open. The best general upper bound has been improved from $n^2/2 - O(n)$ to $n^2/4 - \Theta(n)$ (Bannister et al., 2014), and the lower bound has been raised from $1.098n$ to $(1.293-o(1))n$ (Scheucher et al., 2019). For restricted classes, linear-size universal point sets of size $2n-2$ have been achieved for bipartite planar graphs and planar graphs of maximum degree 3 (Felsner et al., 2023).
Cited literature (4)
-
Improved the upper bound on universal point set size for all planar graphs from $n^2/2 - O(n)$ to $n^2/4 - \Theta(n)$ via superpatterns, and proved near-linear universal point sets suffice for planar graphs of bounded pathwidth.
-
Proved there is no $n$-universal point set of size $n$ for any $n \geq 15$, and verified via exhaustive search that universal point sets exist for all planar graphs on $n \leq 10$ vertices.
-
Improved the lower bound from $1.235n$ to $(1.293-o(1))n$, and showed by exhaustive computer search that no set of 11 points admits straight-line drawings of all planar graphs on 11 vertices.
-
Constructed an 'exploding double chain' universal point set of size $2n-2$ for bipartite planar graphs and for planar graphs of maximum degree 3, the first linear-size universal point set for classes beyond outerplanar graphs.
Reviewer notes. The $O(n)$ question for ALL planar graphs remains open; the best general bounds are $n^2/4 - \Theta(n)$ (upper) and $(1.293-o(1))n$ (lower). No 2024-2026 breakthroughs were found. The Cardinal et al. 2013 paper is also published as a book chapter (Springer) but the exact conference venue could not be confirmed from a fetched source, so arXiv is listed. The Bannister et al. 2014 JGAA DOI was not directly fetched and is therefore listed as null.
Discussion
More generally, if we let $ f(n) $ denote the size of the smallest $ n $ -universal set, we are interested in the behaviour of $ f $ . The best known upper bound is $ f(n) = O(n^2) $ . Indeed, every $ n $ -vertex planar graph can be drawn as required in the $ n \times n $ grid [dFPP], [S]. On the flip side, it is known that $ f(n) \ge 1.098n $ for sufficiently large $ n $ [CH].
Bibliography
-
[CH]M. Chrobak and H.Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20:83-86, 1989. -
[dFPP]H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid . Combinatorica, 10(1):41-51, 1990. MathSciNet How to draw a planar graph on a grid · MathSciNet -
[S]W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algorithms, pages 138-148, 1990.