Geodesic
$st$-Orientations with Few Transitive Edges
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. 625-650.

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

The problem of orienting the edges of an undirected graph such that the resulting digraph is acyclic and has a single source $s$ and a single sink $t$ has a long tradition in graph theory and is central to many graph drawing algorithms. Such an orientation is called an $st$-orientation. We address the problem of computing $st$-orientations of undirected graphs with the minimum number of transitive edges. We prove that the problem is NP-hard in the general case. For planar graphs we describe an ILP (Integer Linear Programming) model that is fast in practice, namely it takes on average less than 1 second for graphs with up to 100 vertices, and about 10 seconds for larger instances with up to 1000 vertices. We experimentally show that optimum solutions significantly reduce (35% on average) the number of transitive edges with respect to unconstrained $st$-orientations computed via classical $st$-numbering algorithms. Moreover, focusing on popular graph drawing algorithms that apply an $st$-orientation as a preliminary step, we show that reducing the number of transitive edges leads to drawings that are much more compact (with an improvement between 30% and 50% for most of the instances). 
@article{JGAA_2023_27_8_a1,
     author = {Carla Binucci and Walter Didimo and Maurizio Patrignani},
     title = {$st${-Orientations} with {Few} {Transitive} {Edges}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {625--650},
     publisher = {mathdoc},
     volume = {27},
     number = {8},
     year = {2023},
     doi = {10.7155/jgaa.00638},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00638/}
}
TY  - JOUR
AU  - Carla Binucci
AU  - Walter Didimo
AU  - Maurizio Patrignani
TI  - $st$-Orientations with Few Transitive Edges
JO  - Journal of Graph Algorithms and Applications
PY  - 2023
SP  - 625
EP  - 650
VL  - 27
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00638/
DO  - 10.7155/jgaa.00638
LA  - en
ID  - JGAA_2023_27_8_a1
ER  - 
%0 Journal Article
%A Carla Binucci
%A Walter Didimo
%A Maurizio Patrignani
%T $st$-Orientations with Few Transitive Edges
%J Journal of Graph Algorithms and Applications
%D 2023
%P 625-650
%V 27
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00638/
%R 10.7155/jgaa.00638
%G en
%F JGAA_2023_27_8_a1
Carla Binucci; Walter Didimo; Maurizio Patrignani. $st$-Orientations with Few Transitive Edges. 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. 625-650. doi : 10.7155/jgaa.00638. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00638/

Cité par Sources :