Applications of Parameterized st-Orientations in Graph Drawing Algorithms

Papamanthou, Charalampos and Tollis, Ioannis G. (2006) Applications of Parameterized st-Orientations in Graph Drawing Algorithms. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 355-367(Official URL:

Full text not available from this repository.


Many graph drawing algorithms use st-numberings (st-orientations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_32
Classifications: P Styles > P.900 Visibility
M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others

Actions (login required)

View Item View Item