Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00210 Applications of Parameterized st-Orientations Charalampos Papamanthou and Ioannis G. Tollis Vol. 14, no. 2, pp. 337-365, 2010. Regular paper Abstract An st-orientation of a biconnected undirected graph defines a directed graph with no cycles, a single source s and a single sink t. Given an undirected graph G as input, linear-time algorithms have been proposed for computing an st-orientation of G. Such an orientation is useful especially in graph drawing algorithms which use it at their first stage []. Namely, before they process the original undirected graph they receive as input, they transform it into an st-DAG, by computing an st-orientation of it. In this paper we observe that using st-orientations of different longest path lengths in various applications can result in different solutions, each one having its own merit. Guided by this intuition, we present results concerning applications of proposed algorithms for longest path parameterized st-orientations. Specifically, we show how to achieve considerable space savings (e.g., O(n)) for visibility representations of planar graphs by using st-orientations computed by algorithms that can control the length of the longest path. Also, we apply our results to the graph coloring problem, where we use an st-orientation as an intermediate step to compute a good coloring of a graph, and to other problems, such as computing space-efficient orthogonal drawings and longest paths.
|
Published: June 2010. Accepted: April 2010. Submitted: December 2008. Final: June 2010. Revised: December 2009. Reviewed: May 2009. Communicated by Ulrik Brandes |
| Journal of Graph Algorithms and Applications |