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.


Every three-connected planar graph with n vertices has a drawing on an O(n7/3O(n7/3) 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 well 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) 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(n2) ×O(n2) grid.

  PostScript file (gzipped)
other papers about this subject
Last update: April 5, 2005.