Parameterized st-Orientations of Graphs: Algorithms and Experiments

Papamanthou, Charalampos and Tollis, Ioannis G. (2007) Parameterized st-Orientations of Graphs: Algorithms and Experiments. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 220-233 (Official URL:

Full text not available from this repository.


st-orientations (st-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 st-orientation of a biconnected graph. However, as indicated in [1], the computation of more than one st-orientation is very important for many applications in multiple research areas, such as this of Graph Drawing. In this paper we show how to compute such orientations with certain (parameterized) characteristics in the final st-oriented graph, such as the length of the longest path. Apart from Graph Drawing, this work applies in other areas such as Network Routing and in tackling difficult problems such as Graph Coloring and Longest Path. We present primary approaches to the problem of computing longest path parameterized st-orientations of graphs, an analytical presentation (together with proof of correctness) of a new $O(m\log^5 n)$ ($O(m\log n)$ for planar graphs) time algorithm that computes such orientations (and which was used in [1]) and extensive computational results that reveal the robustness of the algorithm.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_22
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:777

Repository Staff Only: item control page


C. Papamanthou and I.G. Tollis. Applications of parameterized st-orientations in graph drawing algorithms. In LNCS Graph Drawing 2004, volume 3843, pages 355-367, 2005.

R. Tamassia and I.G. Tollis. A unied approach to visibility representations of planar graphs. Disc. and Comp. Geom., 1:321-341, 1986.

A. Papakostas and I.G. Tollis. Algorithms for area-ecient orthogonal drawings. Computational Geometry: Theory and Applications, 9:83-110, 1998.

G.D. Battista, P. Eades, R. Tamassia, and I.G. Tollis. Annotated bibliography on graph drawing algorithms. Computational Geometry: Theory and Applications, 4:235-282, 1994.

G.D. Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. on Systems, Man, and Cybernetics, SMC-11(2):109-125, 1981.

F. Annexstein and K. Berman. Directional routing via generalized st-numberings. SIAM J. Discrete Math., 13(2):268-279, 2000.

M. Mursalin Akon, S. Asaduzzaman, M.S. Rahman, and M. Matsumoto. Proposal for st-routing. Tellecommunication Systems, 25(3-4):287-298, 2004.

S. Nakano, M.S. Rahman, and T. Nishizeki. A linear-time algorithm for four-partitioning four-connected planar graphs. Information Processing Letters, 62:315-322, 1997.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In P. Rosenstiehl(ed.) Theory of Graphs: Tihany, Academic Press, New York, pages 115-118, 1968.

S. Even and R. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339-344, 1976.

J. Ebert. st-ordering the vertices of biconenected graphs. Computing, 30(1):19-33, 1983.

R. Tarjan. Two streamlined depth-rst search algorithms. Fundamentae Informatica, 9:85-94, 1986.

P. Rosenstiehl and R. Tarjan. Rectilinear planar layout and bipolar orientation of planar graphs. Discrete Comput. Geom., 1:343-353, 1986.

Y. Maon, B. Schieber, and U. Vishkin. Parallel ear decomposition search (eds) and st-numbering in graphs. Theoret. Comput. Sci, 47:277-298, 1986.

Ulrik Brandes. Eager st-ordering. In LNCS ESA 2002, volume 2461, pages 247-256, 2002.

H.D. Fraysseix, P.O. de Mendez, and P. Rosenstiehl. Bipolar orientations revisited. Discrete Applied Mathematics, 56:157-179, 1995.

C. Papamanthou and I.G. Tollis. st-numberings and longest paths, manuscript, ICS-FORTH 2004.

J. Hopcroft and R. Tarjan. Ecient algorithms for graph manipulation. Comm. ACM, 16:372-378, 1973.

J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge and biconnectivity. J. ACM, 48(4):723-760, 2001.

Tams Lukovszki and Willy-B. Strothmann. Decremental biconnectivity on planar graphs technical report, university of paderborn, tr-ri-97-186.

T. Gallai. On directed paths and circuits. In P. Erdos(ed.) Theory of Graphs: International Symposium July 1966, pages 215-232, 1967.