An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs

Alexander Choi, Marek Chrobak, Kevin Costello

A set $U\subseteq {\mathbb{R}}^2$ is $n$-universal if all $n$-vertex planar graphs have a planar straight-line embedding into $U$. We prove that if $Q\subseteq {\mathbb{R}}^2$ consists of poi…