Convexity-Increasing Morphs of Planar Graphs

02/19/2018
by   Linda Kleist, et al.
0

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of a 3-connected graph, we show how to morph the drawing to one with convex faces while maintaining planarity at all times. Furthermore, the morph is convexity increasing, meaning that angles of inner faces never change from convex to reflex. We give a polynomial time 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset