Series-parallel orientations preserving the cycle-radius

Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of G. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel.

► We define the cycle-radius of a graph and use it as a measure for the quality of an orientation of the graph. ► This concept is useful when orienting an undirected graph while minimizing the resulting diameter. ► It also provides a new characterization of series-parallel graphs.