Benvenuti nell'Anagrafe della Ricerca d'Ateneo
La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.
EnglishGiven an n-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of O(n) steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns’ 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps.
Alamdari, S., Angelini, P., Barrera Cruz, F., Chan, T.M., Da Lozzo, G., Di Battista, G., et al. (2017). How to Morph Planar Graph Drawings. SIAM JOURNAL ON COMPUTING, 46(2), 824-852 [10.1137/16M1069171].
| Titolo: | How to Morph Planar Graph Drawings | |
| Autori: | ||
| Data di pubblicazione: | 2017 | |
| Rivista: | ||
| Citazione: | Alamdari, S., Angelini, P., Barrera Cruz, F., Chan, T.M., Da Lozzo, G., Di Battista, G., et al. (2017). How to Morph Planar Graph Drawings. SIAM JOURNAL ON COMPUTING, 46(2), 824-852 [10.1137/16M1069171]. | |
| Abstract: | Given an n-vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous transformation) between the two drawings that preserves straight-line planarity and consists of O(n) steps, which we prove is optimal in the worst case. Each step is a unidirectional linear morph, which means that every vertex moves at constant speed along a straight line, and the lines are parallel although the vertex speeds may differ. Thus we provide an efficient version of Cairns’ 1944 proof of the existence of straight-line planarity-preserving morphs for triangulated graphs, which required an exponential number of steps. | |
| Handle: | http://hdl.handle.net/11590/316742 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Note | Licenza | |
|---|---|---|---|---|---|
| SICOMP-Published.pdf | Versione Editoriale (PDF) | Nessuna Nota | DRM non definito | Open Access Visualizza/Apri |
http://hdl.handle.net/11590/316742
Copyright © 2022