DOI

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.

Язык оригиналаанглийский
Название основной публикацииWALCOM
Подзаголовок основной публикацииAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
РедакторыPetra Mutzel, Md. Saidur Rahman, Slamin
ИздательSpringer Nature
Страницы85-96
Число страниц12
ISBN (электронное издание)978-3-030-96731-4
ISBN (печатное издание)978-3-030-96730-7
DOI
СостояниеОпубликовано - 23 мар 2022
СобытиеWALCOM 2022 - Jember, Индонезия
Продолжительность: 24 мар 202226 мар 2022
https://walcom2022.unej.ac.id

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том13174 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференцияWALCOM 2022
Страна/TерриторияИндонезия
ГородJember
Период24/03/2226/03/22
Сайт в сети Internet

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 97470930