Morphing Planar Graph Drawings Through 3D

Authors

  • Kevin Buchin Technische Universität Dortmund
  • Will Evans University of British Columbia
  • Fabrizio Frati Roma Tre University
  • Irina Kostitsyna TU Eindhoven
  • Maarten Löffler Utrecht University
  • Tim Ophelders Utrecht University and TU Eindhoven
  • Alexander Wolff Universität Würzburg

DOI:

https://doi.org/10.57717/cgt.v2i1.33

Abstract

In this paper, we investigate crossing-free 3D morphs between planar straight-line drawings. We show that, for any two (not necessarily topologically equivalent) planar straight-line drawings of an n-vertex planar graph, there exists a piecewise-linear crossing-free 3D morph with O(n2) steps that transforms one drawing into the other. We also give some evidence why it is difficult to obtain a linear lower bound (which exists in 2D) for the number of steps of a crossing-free 3D morph.

Downloads

Published

2023-09-22

How to Cite

Buchin, K., Evans, W., Frati, F., Kostitsyna, I., Löffler, M., Ophelders, T., & Wolff, A. (2023). Morphing Planar Graph Drawings Through 3D. Computing in Geometry and Topology, 2(1), 5:1–5:18. https://doi.org/10.57717/cgt.v2i1.33

Issue

Vol. 2 No. 1 (2023)

Section

Original Research Articles

Categories

License

Copyright (c) 2023 Kevin Buchin, Will Evans, Fabrizio Frati, Irina Kostitsyna, Maarten Loffler, Tim Ophelders, Alexander Wolff

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).