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, Limerick, Ireland , pp. 355-367 (Official URL: http://dx.doi.org/10.1007/11618058_32).

Full text not available from this repository.

Abstract

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
ID Code:704

Repository Staff Only: item control page

References

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

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

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

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

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. P. Rosestiehl(ed.) Theory of Graphs: International Symposium July 1966, pages 215-232, 1967.

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

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

P. Rosehnstiehl 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.

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.: Algorithms for parameterized st-orientations of graphs, manuscript, 2005.

J. Hopcroft and R. Tarjan.: Efficient 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.

Michael T. Goodrich and Roberto Tamassia.: Data Structures and Algorithms in Java. John Wiley, 2 edition, 2001.