Morphing Planar Graph Drawings Through 3D
- Kevin Buchin,
- William S. Evans,
- Fabrizio Frati,
- Irina Kostitsyna,
- Maarten Löffler,
Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-reviewOpen access
Information
Output type
Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-reviewHost publication Subtitle
Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, ProceedingsOriginal language
EnglishPages from-to (Number of pages)
Pages 80-95 (16 pages)Publication milestones
- Published - 2023
Publication status
Published - 2023
Publisher
Springer, Netherlands, United States, United Kingdom, Germany, Italy, France, Austria, India, Switzerland, China, JapanPublication series
- Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print): 0302-9743
ISSN (Electronic): 1611-3349
Volume: 13878 LNCS
ISBN (Print)
9783031231001Host publication title
SOFSEM 2023Host publication editors
- Leszek Gasieniec
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.
Documents and Links
Metrics
Metrics
SciVal
citations
3
SciVal
FWCI
0.75
SciVal
Author count
7
SciVal
Paper percentile
63
Scopus
citations
3
PlumX, opens in new tab
Citation count
3
