Imre Bárány and Günter Rote:
Strictly convex drawings of planar graphs
Documenta
Mathematica 11 (2006), 369–391.
→BibTeX
Abstract
Every three-connected planar graph with n vertices has a
drawing on an
O(n2)×O(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/3)×O(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
Erratum
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.