TY - JOUR T1 - Algorithms for computing a parameterized st-orientation JF - Theoretical Computer Science Y1 - 2008 A1 - Charalampos Papamanthou A1 - Tollis, Ioannis G. KW - Graph algorithms KW - Longest path KW - Planar graphs KW - s t -numberings AB - s t -orientations ( s t -numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an s t -orientation of a biconnected graph. In this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final s t -oriented graph, such as the length of the longest path. This work has many applications, including Graph Drawing and Network Routing, where the length of the longest path is vital in deciding certain features of the final solution. This work applies to other difficult problems as well, such as graph coloring and of course longest path. We present extended theoretical and experimental results which show that our technique is efficient and performs well in practice. VL - 408 SN - 0304-3975 UR - http://www.sciencedirect.com/science/article/pii/S0304397508005653 CP - 2–3 J1 - Theoretical Computer Science ER -