## Günter Rote:

# Strictly convex drawings of planar graphs

*In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Vancouver, January 2005, pp. 728-734.
*
### Abstract

Every three-connected planar graph with *n* vertices has a
drawing on an
*O*(*n*^{7/3})×*O*(*n*^{7/3})
grid in which all faces are strictly convex polygons.
More generally, a strictly convex drawing exists on a grid
of size *O*(*n*^{2}*s*^{2}) ×*O*(*n*^{5/2}/*s*),
for any choice of a parameter
*s* in the range 1 < *s* < *n*^{1/6}, as
well
as on an
*O*(*n*) ×*O*(*n*^{3}) grid.
These drawings are obtained by perturbing (not strictly) convex
drawings, which are known to exist on *O*(*n*) ×*O*(*n*)
grids.
The analysis
of the perturbation leads to a number-theoretic question from the
geometry of numbers whose solution would yield grid drawings on an
*O*(*n*^{2}) ×*O*(*n*^{2})
grid.

Last update: April 5, 2005.