Strictly Convex Drawings of Planar Graphs

Every three-connected planar graph with $n$ vertices has a drawing on an $O(n^2) \times 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) \times 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.

2000 Mathematics Subject Classification: Primary 05C62; Secondary 52C05.

Keywords and Phrases: Graph drawing, planar graphs.

Full text: dvi.gz 39 k, dvi 87 k, ps.gz 777 k, pdf 454 k.

Home Page of DOCUMENTA MATHEMATICA