×

Strictly convex drawings of planar graphs. (English) Zbl 1108.05065

Summary: 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.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
52C05 Lattices and convex bodies in \(2\) dimensions (aspects of discrete geometry)

Keywords:

convex polygons
PDFBibTeX XMLCite
Full Text: EuDML EMIS