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

# Strictly convex drawings of planar graphs

*Documenta
Mathematica 11 (2006), 369–391.
*
### Abstract

Every three-connected planar graph with *n* vertices has a
drawing on an
*O*(*n*^{2})×*O*(*n*^{2})
grid in which all faces are strictly convex
polygons. More
generally, there is a drawing on an
*O*(*nw*) ×*O*(*n*^{3}/*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 an explicit lower bound on the number of
primitive vectors in a triangle.

As an auxiliary result, we prove that the right triangle (0,0),(`a`,0),(`a`,`b`)
contains at least `a``b`/4 primitive vectors, for every integer `a`≥1 and every
`b`≥2.

### Erratum:

The paper 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ć.
This paper improves a conference paper by the second author with the
same title,
in which a weaker bound of
*O*(*n*^{7/3})×*O*(*n*^{7/3})
on the grid size had been established:

## Günter Rote:
Strictly convex drawings of planar graphs

*Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Vancouver, January 2005, pp. 728–734.
*
Last update: September 29, 2011.