Strictly convex drawings of planar graphs

Imre Barany, Guenter Rote

Every three-connected planar graph with n vertices has a drawing on an O(n^2) x O(n^2) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbi…