Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 мар 2022 → 26 мар 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/22 → 26/03/22 |
Сайт в сети Internet |
ID: 97470930