On st-orientations and st-numberings of planar graphs

Abstract

An st-graph is a directed, acyclic graph with a single source s and a single sink t. An st-orientation of a graph G is an assignment of directions to its edges such that G becomes an st-graph. An st-numbering of a biconnected undirected graph G having n vertices is a numbering of its vertices by integers 1,2, ... ,n such that a vertex s receives number 1, a vertex t receives number n and every other vertex of G is adjacent to at least one lower-numbered vertex and at least one higher-numbered vertex. An st-orientation of a graph G can be produced from an st-numbering of G. st-Orientations and st-numberings have many applications in graph drawings such as in hierarchical drawings, in visibility drawings' and in orthogonal drawings. Controlling the length of the longest path in an orientation has a very important role in the applications mentioned above. But most of the known algorithms for constructing an st-orientation of a graph G do not have any special feature like controlling the length of the longest-path in the orientation, Moreover, majority of the applications of st-orientation, where controlling the length of the longest path is required in the orientation, arise in the area of planar graphs. Hence an efficient algorithm is required to construct an st-orientation for a planar graph where the length of the longest path can be controlled. In this thesis we present a new linear-time algorithm for computing an st-orientation of a planar graph with certain characteristics. This algorithm have the feature of controlling the length of the longest path in the st-orientation. We also present algorithms which can construct st-orientation having comparably long or short longest paths. In this thesis we . also have studied st-orientation of a special class of graphs called series-parallel graphs.