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