Standard

Morphing Tree Drawings in a Small 3D Grid. / Истомина, Александра Андреевна; Арсеньева, Елена Александровна; Гангопадхай, Рауль.

WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. ed. / Petra Mutzel; Md. Saidur Rahman; Slamin. Springer Nature, 2022. p. 85-96 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13174 LNCS).

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

Harvard

Истомина, АА, Арсеньева, ЕА & Гангопадхай, Р 2022, Morphing Tree Drawings in a Small 3D Grid. in P Mutzel, MS Rahman & Slamin (eds), WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13174 LNCS, Springer Nature, pp. 85-96, WALCOM 2022, Jember, Indonesia, 24/03/22. https://doi.org/10.48550/arXiv.2106.04289, https://doi.org/10.1007/978-3-030-96731-4_8

APA

Истомина, А. А., Арсеньева, Е. А., & Гангопадхай, Р. (2022). Morphing Tree Drawings in a Small 3D Grid. In P. Mutzel, M. S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings (pp. 85-96). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13174 LNCS). Springer Nature. https://doi.org/10.48550/arXiv.2106.04289, https://doi.org/10.1007/978-3-030-96731-4_8

Vancouver

Истомина АА, Арсеньева ЕА, Гангопадхай Р. Morphing Tree Drawings in a Small 3D Grid. In Mutzel P, Rahman MS, Slamin, editors, WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. Springer Nature. 2022. p. 85-96. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.48550/arXiv.2106.04289, https://doi.org/10.1007/978-3-030-96731-4_8

Author

Истомина, Александра Андреевна ; Арсеньева, Елена Александровна ; Гангопадхай, Рауль. / Morphing Tree Drawings in a Small 3D Grid. WALCOM: Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings. editor / Petra Mutzel ; Md. Saidur Rahman ; Slamin. Springer Nature, 2022. pp. 85-96 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{961103c1903f4af8841ea07a2f178644,
title = "Morphing Tree Drawings in a Small 3D Grid",
abstract = "We study crossing-free grid morphs for planar tree drawings using the third dimension. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. There is a crossing-free morph between two drawings of an n-vertex planar graph G with O(n) morphing steps, and using the third dimension the number of steps can be reduced to O(log n) for an n-vertex tree [Arseneva et al. 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We present a 3D crossing-free morph between two planar grid drawings of an n-vertex tree in O(nlogn) morphing steps. Each intermediate drawing lies in a 3D grid of polynomial volume.",
keywords = "3D morphing, bounded resolution, morphing grid drawings",
author = "Истомина, {Александра Андреевна} and Арсеньева, {Елена Александровна} and Рауль Гангопадхай",
note = "Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; null ; Conference date: 24-03-2022 Through 26-03-2022",
year = "2022",
month = mar,
day = "23",
doi = "10.48550/arXiv.2106.04289",
language = "English",
isbn = "978-3-030-96730-7",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "85--96",
editor = "Petra Mutzel and Rahman, {Md. Saidur} and Slamin",
booktitle = "WALCOM",
address = "Germany",
url = "https://walcom2022.unej.ac.id",

}

RIS

TY - GEN

T1 - Morphing Tree Drawings in a Small 3D Grid

AU - Истомина, Александра Андреевна

AU - Арсеньева, Елена Александровна

AU - Гангопадхай, Рауль

N1 - Publisher Copyright: © 2022, Springer Nature Switzerland AG.

PY - 2022/3/23

Y1 - 2022/3/23

N2 - We study crossing-free grid morphs for planar tree drawings using the third dimension. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. There is a crossing-free morph between two drawings of an n-vertex planar graph G with O(n) morphing steps, and using the third dimension the number of steps can be reduced to O(log n) for an n-vertex tree [Arseneva et al. 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We present a 3D crossing-free morph between two planar grid drawings of an n-vertex tree in O(nlogn) morphing steps. Each intermediate drawing lies in a 3D grid of polynomial volume.

AB - We study crossing-free grid morphs for planar tree drawings using the third dimension. A morph consists of morphing steps, where vertices move simultaneously along straight-line trajectories at constant speeds. There is a crossing-free morph between two drawings of an n-vertex planar graph G with O(n) morphing steps, and using the third dimension the number of steps can be reduced to O(log n) for an n-vertex tree [Arseneva et al. 2019]. However, these morphs do not bound one practical parameter, the resolution. Can the number of steps be reduced substantially by using the third dimension while keeping the resolution bounded throughout the morph? We present a 3D crossing-free morph between two planar grid drawings of an n-vertex tree in O(nlogn) morphing steps. Each intermediate drawing lies in a 3D grid of polynomial volume.

KW - 3D morphing

KW - bounded resolution

KW - morphing grid drawings

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

U2 - 10.48550/arXiv.2106.04289

DO - 10.48550/arXiv.2106.04289

M3 - Conference contribution

SN - 978-3-030-96730-7

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

SP - 85

EP - 96

BT - WALCOM

A2 - Mutzel, Petra

A2 - Rahman, Md. Saidur

A2 - Slamin, null

PB - Springer Nature

Y2 - 24 March 2022 through 26 March 2022

ER -

ID: 97470930