Convexity-Increasing Morphs of Planar Graphs

Abstract

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.