DIKUL - logo
E-resources
Peer reviewed Open access
  • Convexity-increasing morphs...
    Kleist, Linda; Klemz, Boris; Lubiw, Anna; Schlipf, Lena; Staals, Frank; Strash, Darren

    Computational geometry, November 2019, 2019-11-00, Volume: 84
    Journal Article

    We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of an internally 3-connected graph, we show how to morph the drawing to one with strictly convex faces while maintaining planarity at all times. Our morph is convexity-increasing, meaning that once an angle is convex, it remains convex. We give an efficient algorithm that constructs such a morph as a composition of a linear number of steps where each step either moves vertices along horizontal lines or moves vertices along vertical lines. Moreover, we show that a linear number of steps is worst-case optimal. To obtain our result, we use a well-known technique by Hong and Nagamochi for finding redrawings with convex faces while preserving y-coordinates. Using a variant of Tutte's graph drawing algorithm, we obtain a new proof of Hong and Nagamochi's result which comes with a better running time. This is of independent interest, as Hong and Nagamochi's technique serves as a building block in existing morphing algorithms.