  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 model that is fast in practice. We
experimentally show that optimum solutions dramatically reduce 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.
