Home Issues About JGAA Instructions for Authors
 
 
Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
DOI: 10.7155/jgaa.00595
On Turn-Regular Orthogonal Representations
Vol. 26, no. 3, pp. 285-306, 2022. Regular paper.
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 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.
 This work is licensed under the terms of the CC-BY license.
Submitted: November 2020.
Reviewed: May 2022.
Revised: May 2022.
Accepted: May 2022.
Final: June 2022.
Published: June 2022.
Communicated by David Auber and Pavel Valtr
article (PDF)
BibTeX