How many vertex locations can be arbitrarily chosen when drawing planar graphs?

Abstract

It is proven that every set $S$ of distinct points in the plane with cardinality $\lceil \frac{\sqrt{{\log }_{2}n}-1}{4}\rceil$ can be a subset of the vertices of a crossing-free straight-line drawing of any planar graph with $n$ vertices. It is also proven that if $S$ is restricted to be a one-sided convex point set, its cardinality increases to $\lceil \sqrt[3]{n}\rceil$. The proofs are constructive and give rise to O(n)-time drawing algorithms. As a part of our proofs, we show that every maximal planar graph contains a large induced biconnected outerplanar graphs and a large induced outerpath (an outerplanar graph whose weak dual is a path).