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(n^2)$ 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.
%0 Journal Article
%1 befklow-mpgdt3d-CGT23
%A Buchin, Kevin
%A Evans, Will
%A Frati, Fabrizio
%A Kostitsyna, Irina
%A Löffler, Maarten
%A Ophelders, Tim
%A Wolff, Alexander
%D 2023
%J Computing in Geometry and Topology
%K 2D 3D graph_drawing morphing myown piecewise_linear_morph
%N 1
%P 5:1--5:18
%R 10.57717/cgt.v2i1.33
%T Morphing Planar Graph Drawings Through 3D
%V 2
%X 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(n^2)$ 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.
@article{befklow-mpgdt3d-CGT23,
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(n^2)$ 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.},
added-at = {2024-04-29T21:12:31.000+0200},
author = {Buchin, Kevin and Evans, Will and Frati, Fabrizio and Kostitsyna, Irina and Löffler, Maarten and Ophelders, Tim and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/25bbe67d54c0837b2c36a6da22249e8ec/awolff},
doi = {10.57717/cgt.v2i1.33},
interhash = {4be472cf9681cb6df6cb0e34e48eadd7},
intrahash = {5bbe67d54c0837b2c36a6da22249e8ec},
journal = {Computing in Geometry and Topology},
keywords = {2D 3D graph_drawing morphing myown piecewise_linear_morph},
number = 1,
pages = {5:1--5:18},
slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/befklow-mpgdt3d-SOFSEM23-slides.pdf},
timestamp = {2024-04-29T21:12:31.000+0200},
title = {Morphing Planar Graph Drawings Through {3D}},
volume = 2,
year = 2023
}