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.
Every three-connected planar graph with n vertices has a
drawing on an
grid in which all faces are strictly convex polygons.
More generally, a strictly convex drawing exists on a grid
of size O(n2s2) ×O(n5/2/s),
for any choice of a parameter
s in the range 1 < s < n1/6, as
as on an
O(n) ×O(n3) grid.
These drawings are obtained by perturbing (not strictly) convex
drawings, which are known to exist on O(n) ×O(n)
of the perturbation leads to a number-theoretic question from the
geometry of numbers whose solution would yield grid drawings on an
Last update: April 5, 2005.