Applications of Parameterized st-Orientations

Charalampos Papamanthou ; Ioannis Tollis

Journal of Graph Algorithms and Applications, Tome 14 (2010) no. 2, pp. 337-365.

Résumé

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.

Détail

DOI : 10.7155/jgaa.00210

Keywords: st-numbering, acyclic orientation, visibility representation, graph coloring, orthogonal drawing