Strictly convex drawings of planar graphs

Abstract

Every three-connected planar graph with $n$ vertices has a drawing on an $O(n^2) \times O(n^2)$ grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings on $O(n) \times O(n)$ grids. Tighter bounds are obtained when the faces have fewer sides. In the proof, we derive an explicit lower bound on the number of primitive vectors in a triangle.