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.
EnglishAn interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that “point to each other” inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with “small” faces has a turn-regular orthogonal representation without bends.
Bekos, M.A., Binucci, C., Di Battista, G., Didimo, W., Gronemann, M., Klein, K., et al. (2020). On Turn-Regular Orthogonal Representations. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.250-264). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_20].
| Titolo: | On Turn-Regular Orthogonal Representations | |
| Autori: | ||
| Data di pubblicazione: | 2020 | |
| Serie: | ||
| Citazione: | Bekos, M.A., Binucci, C., Di Battista, G., Didimo, W., Gronemann, M., Klein, K., et al. (2020). On Turn-Regular Orthogonal Representations. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.250-264). Springer Science and Business Media Deutschland GmbH [10.1007/978-3-030-68766-3_20]. | |
| Handle: | http://hdl.handle.net/11590/385597 | |
| ISBN: | 978-3-030-68765-6 | |
| Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
Copyright © 2021