Strictly convex drawings of planar graphs
| dc.creator | Barany, Imre | |
| dc.creator | Rote, Guenter | |
| dc.date | 2005-07-11 | |
| dc.date | 2006-06-21 | |
| dc.date.accessioned | 2026-07-07T07:37:44Z | |
| dc.date.available | 2026-07-07T07:37:44Z | |
| dc.description | Every three-connected planar graph with n vertices has a drawing on an O(n^2) x O(n^2) grid in which all faces are strictly convex polygons. These drawings are obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids. More generally, a strictly convex drawing exists on a grid of size O(W) x O(n^4/W), for any choice of a parameter W in the range n<W<n^2. 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. | |
| dc.description | 20 pages, 13 figures. to be published in Documenta Mathematica. The revision includes numerous small additions, corrections, and improvements, in particular: - a discussion of the constants in the O-notation, after the statement of thm.1. - a different set-up and clarification of the case distinction for Lemma 1 | |
| dc.identifier | https://arxiv.org/abs/cs/0507030 | |
| dc.identifier | http://arxiv.org/abs/cs/0507030 | |
| dc.identifier | DOCUMENTA MATHEMATICA, Vol. 11 (2006), 369-391 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/120876 | |
| dc.subject | Computational Geometry | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2; G.2.2 | |
| dc.title | Strictly convex drawings of planar graphs | |
| dc.type | text |