Optimal st-orientations for plane triangulations

For plane triangulations, it has been proved that there exists a plane triangulation G with n vertices such that for any st-orientation of G, the length of the longest directed paths of G in the st-orientation is ≥ [2n/3] (Zhang and He in Lecture Notes in Computer Science, vol. 3383, pp. 425-430, 2005). In this paper, we prove the bound 2n 3 is optimal by showing that every plane triangulation G with nvertices admits an st-orientation with the length of its longest directed paths bounded by 2n/3 + O(1). In addition, this st-orientation is constructible in linear time. A byproduct of this result is that every plane graph G with n vertices admits a visibility representation with height ≤ 2n/3 + O(1), constructible in linear time, which is also optimal.