Morphing Planar Graph Drawings Through 3D

التفاصيل البيبلوغرافية
العنوان: Morphing Planar Graph Drawings Through 3D
المؤلفون: Buchin, Kevin, Evans, Will, Frati, Fabrizio, Kostitsyna, Irina, Löffler, Maarten, Ophelders, Tim, Wolff, Alexander
سنة النشر: 2022
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Computational Geometry, Computer Science - Data Structures and Algorithms
الوصف: 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.
نوع الوثيقة: Working Paper
الوصول الحر: http://arxiv.org/abs/2210.05384Test
رقم الانضمام: edsarx.2210.05384
قاعدة البيانات: arXiv