Morphing Planar Graph Drawings Through 3D

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.

keywords: Computational Geometry, Graph Drawing, Graphs Theory, Higher Dimensions

Journal Article (peer-reviewed)

Alexander Wolff, Fabrizio Frati, Irina Kostitsyna, Kevin Buchin, Maarten Löffler, Tim Ophelders, Will Evans
Morphing Planar Graph Drawings Through 3D
Computing in Geometry and Topology
2, 1, 2023
https://doi.org/10.57717/cgt.v2i1.33

Conference Proceedings (peer-reviewed)

Alexander Wolff, Fabrizio Frati, Irina Kostitsyna, Kevin Buchin, Maarten Löffler, Tim Ophelders, Will Evans
Morphing Planar Graph Drawings Through 3D
Proc. 48th International Conference on Current Trends in Theory and Practice of Computer Science
(to appear), 2023

back to list