• Elena Arseneva
  • Prosenjit Bose
  • Pilar Cano
  • Anthony D’Angelo
  • Vida Dujmović
  • Fabrizio Frati
  • Stefan Langerman
  • Alessandra Tappini

We study the question whether a crossing-free 3D morph between two straight-line drawings of an n-vertex tree can be constructed consisting of a small number of linear morphing steps. We look both at the case in which the two given drawings are two-dimensional and at the one in which they are three-dimensional. In the former setting we prove that a crossing-free 3D morph always exists with O(log n) steps, while for the latter Θ(n) steps are always sufficient and sometimes necessary.

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 26th International Symposium, GD 2018, Proceedings
EditorsTherese Biedl, Andreas Kerren
PublisherSpringer Nature
Pages371-384
Number of pages14
ISBN (Print)9783030044138
DOIs
StatePublished - 1 Jan 2018
Event26th International Symposium on Graph Drawing and Network Visualization, GD 2018 - Barcelona, Spain
Duration: 26 Sep 201828 Sep 2018

Publication series

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

Conference

Conference26th International Symposium on Graph Drawing and Network Visualization, GD 2018
Country/TerritorySpain
CityBarcelona
Period26/09/1828/09/18

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 39288412