Geodesic
On Turn-Regular Orthogonal Representations
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020 , Tome 26 (2022) no. 3, pp. 285-306.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00595
Keywords: Orthogonal Drawings, Turn-regularity, Compaction 
@article{JGAA_2022_26_3_a1,
     author = {Michael Bekos and Carla Binucci and Giuseppe Di Battista and Walter Didimo and Martin Gronemann and Karsten Klein and Maurizio Patrignani and Ignaz Rutter},
     title = {On {Turn-Regular} {Orthogonal} {Representations}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {285--306},
     publisher = {mathdoc},
     volume = {26},
     number = {3},
     year = {2022},
     doi = {10.7155/jgaa.00595},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00595/}
}
TY  - JOUR
AU  - Michael Bekos
AU  - Carla Binucci
AU  - Giuseppe Di Battista
AU  - Walter Didimo
AU  - Martin Gronemann
AU  - Karsten Klein
AU  - Maurizio Patrignani
AU  - Ignaz Rutter
TI  - On Turn-Regular Orthogonal Representations
JO  - Journal of Graph Algorithms and Applications
PY  - 2022
SP  - 285
EP  - 306
VL  - 26
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00595/
DO  - 10.7155/jgaa.00595
LA  - en
ID  - JGAA_2022_26_3_a1
ER  - 
%0 Journal Article
%A Michael Bekos
%A Carla Binucci
%A Giuseppe Di Battista
%A Walter Didimo
%A Martin Gronemann
%A Karsten Klein
%A Maurizio Patrignani
%A Ignaz Rutter
%T On Turn-Regular Orthogonal Representations
%J Journal of Graph Algorithms and Applications
%D 2022
%P 285-306
%V 26
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00595/
%R 10.7155/jgaa.00595
%G en
%F JGAA_2022_26_3_a1
Michael Bekos; Carla Binucci; Giuseppe Di Battista; Walter Didimo; Martin Gronemann; Karsten Klein; Maurizio Patrignani; Ignaz Rutter. On Turn-Regular Orthogonal Representations. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-eighth International Symposium on Graph Drawing and Network Visualization, GD 2020
					, Tome 26 (2022) no. 3, pp. 285-306. doi : 10.7155/jgaa.00595. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00595/

Cité par Sources :