Veröffentlichung

Titel:

Convexity-Increasing Morphs of Planar Graphs

AutorInnen:

Boris Klemz
Linda Kleist
Anna Lubiw
Lena Schlipf
Frank Staals
Darren Strash

Kategorie:

Artikel in Zeitschriften

erschienen in:

Computational Geometry, 84, Seiten 69-88

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.

Download:

arXiv