Convexity-Increasing Morphs of Planar Graphs

Abstract

We study the problem of convexifying drawings of planar graphs. Given any planar straight-line drawing of a 3-connected graph \(G\), 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.

Corresponding Publications

Convexity-Increasing Morphs of Planar Graphs

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

Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science, 2018

Download Local Copy View Slides Export Citation 
@inproceedings{convexmorphing2018,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  booktitle = {Proc. 44th International Workshop on Graph-Theoretic Concepts in Computer Science},
  series = {LNCS},
  volume = {11159},
  year = {2018},
  location = {Cottbus, Germany},
  publisher = {Springer},
  numpages = {12},
  pages = {318--330},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
  doi = {10.1007/978-3-030-00256-5_26},
  url = {https://doi.org/10.1007/978-3-030-00256-5_26},
}

Convexity-Increasing Morphs of Planar Graphs

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

Computational Geometry: Theory and Applications, 2019

Special issue on EuroCG 2018.
Download Local Copy View Slides Export Citation 
@article{convexmorphing2019,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  journal = {Computational Geometry: Theory and Applications},
  year = {2019},
  publisher = {Elsevier},
  project = {convexmorphing2018},
  note = {Special issue on EuroCG 2018.},
  doi = {j.comgeo.2019.07.007},
  pages = {69 -- 88},
  issn = {0925-7721},
  volume = {84},
  url = {https://doi.org/10.1016/j.comgeo.2019.07.007},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
}

Convexity-Increasing Morphs of Planar Graphs

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

Abstr. 34th European Workshop on Computational Geometry (EuroCG), 2018

Invited for a special issue on EuroCG 2018 in Computational Geometry Theory and Applications.
Download Local Copy View Slides Export Citation 
@article{convexmorphing2018_eurocg,
  author = {Kleist, Linda and Klemz, Boris and Lubiw, Anna and Schlipf, Lena
                 and Staals, Frank and Strash, Darren},
  title = {Convexity-Increasing Morphs of Planar Graphs},
  journal = {Abstr. 34th European Workshop on Computational Geometry (EuroCG)},
  year = {2018},
  location = {Berlin, Germany},
  numpages = {6},
  category = {graphs},
  keywords = {planar graphs, graph drawing},
  note = {Invited for a special issue on EuroCG 2018 in Computational Geometry Theory and Applications.},
  project = {convexmorphing2018},
  url = {https://conference.imp.fu-berlin.de/eurocg18/download/eurocg_proc.pdf},
}