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.
