Skip to search boxSkip to navigationSkip to main content

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-review

Open access

Information

Output type

Output:
Chapter in Book/Report/Conference proceeding
Conference contribution
Academic
Peer-review

Host publication Subtitle

Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings

Original language

English

Pages 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, Japan

Publication 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
9783031231001

Host publication title

SOFSEM 2023

Host 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.

Metrics

Metrics

SciVal
citations
3
SciVal
FWCI
0.75
SciVal
Author count
7
SciVal
Paper percentile
63
Scopus
citations
3