Morphing Planar Graph Drawings Through 3D

Kevin Buchin; William S. Evans; Fabrizio Frati; Irina Kostitsyna; Maarten Löffler; Tim Ophelders; Alexander Wolff

doi:10.1007/978-3-031-23101-8_6

Morphing Planar Graph Drawings Through 3D

Kevin Buchin, William S. Evans, Fabrizio Frati, Irina Kostitsyna, Maarten Löffler, Tim Ophelders, Alexander Wolff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

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 ²) 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.

Original language	English
Title of host publication	SOFSEM 2023
Subtitle of host publication	Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings
Editors	Leszek Gasieniec
Publisher	Springer
Pages	80-95
Number of pages	16
ISBN (Print)	9783031231001
DOIs	https://doi.org/10.1007/978-3-031-23101-8_6
Publication status	Published - 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13878 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

3D graph drawing
Linear morph
Morphing steps

Access to Document

10.1007/978-3-031-23101-8_6

Cite this

Buchin, K., Evans, W. S., Frati, F., Kostitsyna, I., Löffler, M., Ophelders, T., & Wolff, A. (2023). Morphing Planar Graph Drawings Through 3D. In L. Gasieniec (Ed.), SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings (pp. 80-95). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13878 LNCS). Springer. https://doi.org/10.1007/978-3-031-23101-8_6

Buchin, Kevin ; Evans, William S. ; Frati, Fabrizio et al. / Morphing Planar Graph Drawings Through 3D. SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings. editor / Leszek Gasieniec. Springer, 2023. pp. 80-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a0d7ac7ce9d54ba6a34c9a4340a67aae,

title = "Morphing Planar Graph Drawings Through 3D",

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.",

keywords = "3D graph drawing, Linear morph, Morphing steps",

author = "Kevin Buchin and Evans, {William S.} and Fabrizio Frati and Irina Kostitsyna and Maarten L{\"o}ffler and Tim Ophelders and Alexander Wolff",

year = "2023",

doi = "10.1007/978-3-031-23101-8_6",

language = "English",

isbn = "9783031231001",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "80--95",

editor = "Leszek Gasieniec",

booktitle = "SOFSEM 2023",

address = "Germany",

}

Buchin, K, Evans, WS, Frati, F, Kostitsyna, I, Löffler, M, Ophelders, T & Wolff, A 2023, Morphing Planar Graph Drawings Through 3D. in L Gasieniec (ed.), SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13878 LNCS, Springer, pp. 80-95. https://doi.org/10.1007/978-3-031-23101-8_6

Morphing Planar Graph Drawings Through 3D. / Buchin, Kevin; Evans, William S.; Frati, Fabrizio et al.
SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings. ed. / Leszek Gasieniec. Springer, 2023. p. 80-95 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13878 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Morphing Planar Graph Drawings Through 3D

AU - Buchin, Kevin

AU - Evans, William S.

AU - Frati, Fabrizio

AU - Kostitsyna, Irina

AU - Löffler, Maarten

AU - Ophelders, Tim

AU - Wolff, Alexander

PY - 2023

Y1 - 2023

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

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

KW - 3D graph drawing

KW - Linear morph

KW - Morphing steps

U2 - 10.1007/978-3-031-23101-8_6

DO - 10.1007/978-3-031-23101-8_6

M3 - Conference contribution

SN - 9783031231001

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 80

EP - 95

BT - SOFSEM 2023

A2 - Gasieniec, Leszek

PB - Springer

ER -

Buchin K, Evans WS, Frati F, Kostitsyna I, Löffler M, Ophelders T et al. Morphing Planar Graph Drawings Through 3D. In Gasieniec L, editor, SOFSEM 2023: Theory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings. Springer. 2023. p. 80-95. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-23101-8_6

Morphing Planar Graph Drawings Through 3D

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this