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

arXiv1908.07097MaRDI QIDQ6323902FDOQ6323902

Authors: Alexander Choi, Marek Chrobak, Kevin P. Costello 

Publication date: 19 August 2019

Abstract: A set $Usubseteqeal{s}^2$ is $n$-universal if all $n$-vertex planar graphs have a planar straight-line embedding into $U$. We prove that if $Qsubseteqeal{s}^2$ consists of points chosen randomly and uniformly from the unit square then $Q$ must have cardinality $Omega(n^2)$ in order to be $n$-universal with high probability. This shows that the probabilistic method, at least in its basic form, cannot be used to establish an $o(n^2)$ upper bound on universal sets.

This page was built for publication: An Omega(n^2) Lower Bound for Random Universal Sets for Planar Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323902)