Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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.
Original language | English |
---|---|
Title of host publication | WALCOM |
Subtitle of host publication | Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings |
Editors | Petra Mutzel, Md. Saidur Rahman, Slamin |
Publisher | Springer Nature |
Pages | 85-96 |
Number of pages | 12 |
ISBN (Electronic) | 978-3-030-96731-4 |
ISBN (Print) | 978-3-030-96730-7 |
DOIs | |
State | Published - 23 Mar 2022 |
Event | WALCOM 2022 - Jember, Indonesia Duration: 24 Mar 2022 → 26 Mar 2022 https://walcom2022.unej.ac.id |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 13174 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | WALCOM 2022 |
---|---|
Country/Territory | Indonesia |
City | Jember |
Period | 24/03/22 → 26/03/22 |
Internet address |
ID: 97470930