Morphing Planar Graph Drawings Through 3D.
Publication date
2022-12-21
Authors
Buchin, Kevin
Evans, William S.
Frati, Fabrizio
Kostitsyna, Irina
Löffler, Maarten
Ophelders, Tim
Wolff, Alexander
Editors
Gąsieniec, Leszek
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
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.
Keywords
Linear morph, 3D graph drawing, Morphing steps, Taverne
Citation
Buchin, K, Evans, W S, Frati, F, Kostitsyna, I, Löffler, M, Ophelders, T & Wolff, A 2022, Morphing Planar Graph Drawings Through 3D. in L Gąsieniec (ed.), SOFSEM 2023: Theory and Practice of Computer Science : 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Nový Smokovec, Slovakia, January 15–18, 2023, Proceedings. 1 edn, Springer, Cham, pp. 80-95. https://doi.org/10.1007/978-3-031-23101-8_6