Veröffentlichung

Titel:

Convexity-Increasing Morphs of Planar Graphs

AutorInnen:

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

Kategorie:

Workshopbeiträge

erschienen in:

Proceedings of the 34th European Workshop on Computational Geometry (EuroCG’18), 2018, invited to the special issue of CGTA on EuroCG'18

Abstract:

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.

Download:

arXiv

BibTeX-Eintrag:

@article{, author = { Boris Klemz and Linda Kleist and Anna Lubiw and Lena Schlipf and Frank Staals and Darren Strash }, title = { Convexity-Increasing Morphs of Planar Graphs }, journal = {Proceedings of the 34th European Workshop on Computational Geometry (EuroCG’18)}, year = {2018}, note ={invited to the special issue of CGTA on EuroCG'18}, }