Imre Bárány and Günter Rote:

Strictly convex drawings of planar graphs

Documenta Mathematica 11 (2006), 369–391.  →BibTeX


Every three-connected planar graph with n vertices has a drawing on an O(n2O(n2) grid in which all faces are strictly convex polygons. More generally, there is a drawing on an O(nw) ×O(n3/w) grid, for any choice of a parameter w in the range 1<w<n.

These drawings are obtained by perturbing (not strictly) convex drawings on O(n) ×O(n) grids. Tighter bounds are obtained when the faces have fewer sides. In the proof, we derive, as an auxiliary result, that the right triangle (0,0),(a,0),(a,b) contains at least ab/4 primitive vectors, for every integer a≥1 and every b≥2.

This paper improves a conference paper by the second author with the same title, in which a weaker bound of O(n7/3O(n7/3) on the grid size had been established:

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.  →BibTeX
  pdf file
other papers about this subject


The paper in Documenta Mathematica gives incorrect authors for reference [1]: On the maximal number of edges of convex digital polygons included into a square grid. The correct authors are Klaus Voss and Reinhard Klette, and the paper is in Russian. The authors of [2] are correctly stated as D. M. Acketa and J. D. Zunić.

Last update: September 29, 2011.