Special issue on Selected papers from the Thirtieth International Symposium on Graph Drawing and Network Visualization, GD 2022
$st$-Orientations with Few Transitive Edges
Vol. 27, no. 8, pp. 625-650, 2023. Regular paper.
Abstract 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).

 This work is licensed under the terms of the CC-BY license.
Submitted: November 2022.
Reviewed: January 2023.
Revised: March 2023.
Accepted: April 2023.
Final: April 2023.
Published: November 2023.
article (PDF)