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 languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
EditorsPetra Mutzel, Md. Saidur Rahman, Slamin
PublisherSpringer Nature
Pages85-96
Number of pages12
ISBN (Electronic)978-3-030-96731-4
ISBN (Print)978-3-030-96730-7
DOIs
StatePublished - 23 Mar 2022
EventWALCOM 2022 - Jember, Indonesia
Duration: 24 Mar 202226 Mar 2022
https://walcom2022.unej.ac.id

Publication series

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

Conference

ConferenceWALCOM 2022
Country/TerritoryIndonesia
CityJember
Period24/03/2226/03/22
Internet address

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

    Research areas

  • 3D morphing, bounded resolution, morphing grid drawings

ID: 97470930