An 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 |