Name
Abstract | ||
|---|---|---|
An st-orientation of a biconnected undirected graph denes a directed graph with no cycles, a single source s and a single sink t. Given an undi- rected 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 rst stage (23). 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 dierent longest path lengths in various applications can result in dierent solutions, each one having its own merit. Guided by this intuition, we present results concerning applications of proposed algorithms for longest path parame- terized st-orientations. Specically, 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 prob- lem, 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-ecient orthogonal drawings and longest paths. |
Year | Venue | Keywords |
|---|---|---|
2010 | J. Graph Algorithms Appl. | planar graph,directed graph,longest path,graph coloring,graph drawing |
Field | DocType | Volume |
Discrete mathematics,Block graph,Comparability graph,Combinatorics,Line graph,Graph property,Biconnected graph,Directed graph,Butterfly graph,Graph (abstract data type),Mathematics | Journal | 14 |
Issue | Citations | PageRank |
2 | 2 | 0.38 |
References | Authors | |
13 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charalampos Papamanthou | 1 | 1109 | 54.41 |
| Ioannis G. Tollis | 2 | 1240 | 162.75 |