Strictly convex drawings of planar graphs
Imre Bárány, Günter Rote · Documenta Mathematica · 2006
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.