Geodesic
Rectilinear Planarity of Partial 2-Trees
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022 , Tome 27 (2023) no. 8, pp. 679-719.

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

A graph is rectilinear planar if it admits a planar orthogonal drawing without bends. While testing rectilinear planarity is NP-hard in general (Garg and Tamassia, 2001), it is a long-standing open problem to establish a tight upper bound on its complexity for partial 2-trees, i.e., graphs whose biconnected components are series-parallel. We describe a new $O(n^2)$-time algorithm to test rectilinear planarity of partial 2-trees, which improves over the current best bound of $O(n^3 \log n)$ (Di Giacomo et al., 2022). Moreover, for partial 2-trees where no two parallel-components in a biconnected component share a pole, we are able to achieve optimal $O(n)$-time complexity. Our algorithms are based on an extensive study and a deeper understanding of the notion of orthogonal spirality, introduced several years ago (Di Battista et al., 1998) to describe how much an orthogonal drawing of a subgraph is rolled-up in an orthogonal drawing of the graph.
DOI : 10.7155/jgaa.00640
Keywords: graph drawing, orthogonal drawing, rectilinear planarity testing, partial 2-trees, series-parallel graphs 
@article{JGAA_2023_27_8_a3,
     author = {Walter Didimo and Michael Kaufmann and Giuseppe Liotta and Giacomo Ortali},
     title = {Rectilinear {Planarity} of {Partial} {2-Trees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {679--719},
     publisher = {mathdoc},
     volume = {27},
     number = {8},
     year = {2023},
     doi = {10.7155/jgaa.00640},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00640/}
}
TY  - JOUR
AU  - Walter Didimo
AU  - Michael Kaufmann
AU  - Giuseppe Liotta
AU  - Giacomo Ortali
TI  - Rectilinear Planarity of Partial 2-Trees
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 679
EP  - 719
VL  - 27
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00640/
DO  - 10.7155/jgaa.00640
LA  - en
ID  - JGAA_2023_27_8_a3
ER  - 
%0 Journal Article
%A Walter Didimo
%A Michael Kaufmann
%A Giuseppe Liotta
%A Giacomo Ortali
%T Rectilinear Planarity of Partial 2-Trees
%J Journal of Graph Algorithms and Applications
%D 2023
%P 679-719
%V 27
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00640/
%R 10.7155/jgaa.00640
%G en
%F JGAA_2023_27_8_a3
Walter Didimo; Michael Kaufmann; Giuseppe Liotta; Giacomo Ortali. Rectilinear Planarity of Partial 2-Trees. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022
					, Tome 27 (2023) no. 8, pp. 679-719. doi : 10.7155/jgaa.00640. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00640/

Cité par Sources :