2024/10/01 by Bekos, Michael, Gronemann, Martin, Montecchiani, Fabrizio +1
paper · doi:10.20382/jocg.v15i1a1
Strictly-convex straight-line drawings of 3-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings of n-vertex graphs is O(n2) × O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non-strictly) convex drawings. Unfortunately, the constants hidden in this area bound are in the order of 104. We present a new and easy-to-implement technique that yields strictly-convex straight-line planar drawings of 3-connected planar graphs on an integer grid of size 2(n-1)× (2n3-n2).