Report Number: CS-TR-75-517
Institution: Stanford University, Department of Computer Science
Title: Distances in orientations of graphs.
Author: Chvatal, Vaclav
Author: Thomassen, Carsten
Date: August 1975
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/517/CS-TR-75-517.pdf