<div class="csl-bib-body">
<div class="csl-entry">Bekos, M. A., Binucci, C., Di Battista, G., Didimo, W., Gronemann, M., Klein, K., Patrignani, M., & Rutter, I. (2022). On Turn-Regular Orthogonal Representations. <i>Journal of Graph Algorithms and Applications</i>, <i>26</i>(3), 285–306. https://doi.org/10.7155/jgaa.00595</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/152301
-
dc.description
Special Issue on the 28th Int. Symposium on Graph Drawing and Network Visualization, GD 2020
-
dc.description.abstract
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 repre-sentations, 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 bi-connected plane graph with “small” faces has a turn-regular orthogonal representation without bends.