Pole dancing: 3D morphs for tree drawings

Elena Arseneva; Prosenjit Bose; Pilar Cano; Anthony D’Angelo; Vida Dujmović; Fabrizio Frati; Stefan Langerman; Alessandra Tappini

doi:10.1007/978-3-030-04414-5_27

Pole dancing: 3D morphs for tree drawings

Elena Arseneva, Prosenjit Bose, Pilar Cano, Anthony D’Angelo, Vida Dujmović, Fabrizio Frati, Stefan Langerman, Alessandra Tappini

Faculty of Mathematics and Mechanics

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

1 Scopus citations

Abstract

We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter Θ(n) steps are always sufficient and sometimes necessary.

Original language	English
Title of host publication	Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings
Editors	Therese Biedl, Andreas Kerren
Publisher	Springer Nature
Pages	371-384
Number of pages	14
ISBN (Print)	9783030044138
DOIs	https://doi.org/10.1007/978-3-030-04414-5_27
State	Published - 1 Jan 2018
Event	26th International Symposium on Graph Drawing and Network Visualization, GD 2018 - Barcelona, Spain Duration: 26 Sep 2018 → 28 Sep 2018

Publication series

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

Conference

Conference	26th International Symposium on Graph Drawing and Network Visualization, GD 2018
Country/Territory	Spain
City	Barcelona
Period	26/09/18 → 28/09/18

Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-04414-5_27

Cite this

Arseneva, E., Bose, P., Cano, P., D’Angelo, A., Dujmović, V., Frati, F., Langerman, S., & Tappini, A. (2018). Pole dancing: 3D morphs for tree drawings. In T. Biedl, & A. Kerren (Eds.), Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings (pp. 371-384). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11282 LNCS). Springer Nature. https://doi.org/10.1007/978-3-030-04414-5_27

Arseneva, Elena ; Bose, Prosenjit ; Cano, Pilar ; D’Angelo, Anthony ; Dujmović, Vida ; Frati, Fabrizio ; Langerman, Stefan ; Tappini, Alessandra. / Pole dancing: 3D morphs for tree drawings. Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. editor / Therese Biedl ; Andreas Kerren. Springer Nature, 2018. pp. 371-384 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9fd5c70fe8504551905abb73df06aec0,

title = "Pole dancing: 3D morphs for tree drawings",

abstract = "We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter Θ(n) steps are always sufficient and sometimes necessary.",

author = "Elena Arseneva and Prosenjit Bose and Pilar Cano and Anthony D{\textquoteright}Angelo and Vida Dujmovi{\'c} and Fabrizio Frati and Stefan Langerman and Alessandra Tappini",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-04414-5_27",

language = "English",

isbn = "9783030044138",

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

publisher = "Springer Nature",

pages = "371--384",

editor = "Therese Biedl and Andreas Kerren",

booktitle = "Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings",

address = "Germany",

note = "26th International Symposium on Graph Drawing and Network Visualization, GD 2018 ; Conference date: 26-09-2018 Through 28-09-2018",

}

Arseneva, E, Bose, P, Cano, P, D’Angelo, A, Dujmović, V, Frati, F, Langerman, S & Tappini, A 2018, Pole dancing: 3D morphs for tree drawings. in T Biedl & A Kerren (eds), Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11282 LNCS, Springer Nature, pp. 371-384, 26th International Symposium on Graph Drawing and Network Visualization, GD 2018, Barcelona, Spain, 26/09/18. https://doi.org/10.1007/978-3-030-04414-5_27

Pole dancing: 3D morphs for tree drawings. / Arseneva, Elena; Bose, Prosenjit; Cano, Pilar; D’Angelo, Anthony; Dujmović, Vida; Frati, Fabrizio; Langerman, Stefan; Tappini, Alessandra.

Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. ed. / Therese Biedl; Andreas Kerren. Springer Nature, 2018. p. 371-384 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11282 LNCS).

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

TY - GEN

T1 - Pole dancing: 3D morphs for tree drawings

AU - Arseneva, Elena

AU - Bose, Prosenjit

AU - Cano, Pilar

AU - D’Angelo, Anthony

AU - Dujmović, Vida

AU - Frati, Fabrizio

AU - Langerman, Stefan

AU - Tappini, Alessandra

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter Θ(n) steps are always sufficient and sometimes necessary.

AB - We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter Θ(n) steps are always sufficient and sometimes necessary.

UR - http://www.scopus.com/inward/record.url?scp=85059074940&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-04414-5_27

DO - 10.1007/978-3-030-04414-5_27

M3 - Conference contribution

AN - SCOPUS:85059074940

SN - 9783030044138

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

SP - 371

EP - 384

BT - Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings

A2 - Biedl, Therese

A2 - Kerren, Andreas

PB - Springer Nature

T2 - 26th International Symposium on Graph Drawing and Network Visualization, GD 2018

Y2 - 26 September 2018 through 28 September 2018

ER -

Arseneva E, Bose P, Cano P, D’Angelo A, Dujmović V, Frati F et al. Pole dancing: 3D morphs for tree drawings. In Biedl T, Kerren A, editors, Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings. Springer Nature. 2018. p. 371-384. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-04414-5_27

Pole dancing: 3D morphs for tree drawings

Abstract

Publication series

Conference

Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this