TY - JOUR
AU - Binucci, Carla
AU - Didimo, Walter
AU - Patrignani, Maurizio
PY - 2023/11/01
Y2 - 2024/09/16
TI - $st$-Orientations with Few Transitive Edges
JF - Journal of Graph Algorithms and Applications
JA - JGAA
VL - 27
IS - 8
SE -
DO - 10.7155/jgaa.00638
UR - https://jgaa.info/index.php/jgaa/article/view/paper638
SP - 625-650
AB - 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).
ER -