Dual circumference and free sets
Pat Morin
Carleton University

For a planar graph $G$, a free set is a subset $F\subset V(G)$ such that, for any set $X$ of $|F|$ points in $\mathbb{R}^2$, there is a non-crossing straight-line drawing of $G$ in which the points in $F$ are drawn on the points of $X$. The existence of large free sets in $n$-vertex planar graphs has been used to give the tightest results for a number of problems in graph drawing and geometric graph theory including untangling, column planarity, universal point subsets, and partial simultaneous geometric drawings. For the last ten years, progress on these problems has been limited by the fact that the best known lower bound on the size of free sets in $n$-vertex planar graphs is $\Omega(n^{0.5})$.

In this talk, I will show that if $G$ is a triangulation of maximum degree $\Delta$ and the dual of $G$ contains a simple cycle of length $\ell$, then $G$ has a free set $F$ of size $\Omega(\ell/\Delta^4)$. This, along with the current best lower-bounds on the circumference of 3-regular 3-connected planar graphs shows that every $n$-vertex planar graph of maximum degree $\Delta$ has a free set of size $\Omega(n^{0.8}/\Delta^4)$. This gives improved results for all the applications mentioned above in the class of planar graphs of bounded degree.