BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-517
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Distances in orientations of graphs.
        TYPE:: Technical Report
      AUTHOR:: Chvatal, Vaclav
      AUTHOR:: Thomassen, Carsten
        DATE:: August 1975
       PAGES:: 25
    ABSTRACT:: We prove that there is a function h(k) such that every
               undirected graph G admits an orientation H with the following
               property: if an edge uv belongs to a cycle of length k in G,
               then uv or vu belongs to a directed cycle of length at most
               h(k) in H. Next, we show that every undirected bridgeless
               graph of radius r admits an orientation of radius at most
               $R^2$+r, and this bound is best possible. We consider the
               same problem with radius replaced by diameter. Finally, we
               show that the problem of deciding whether an undirected graph
               admits an orientation of diameter (resp. radius) two belongs
               to a class of problems called NP-hard.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-517