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
    @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

    Abstr. 34th European Workshop on Computational Geometry (EuroCG), 2018
    Invited for a special issue on EuroCG 2018 in Computational Geometry Theory and Applications.
    @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},
    }