The complexity of two graph orientation problems
We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. Our main result is that for each positive integer k k , there is a linear-time algorithm that decides for a planar graph G G whether there is an orientation for which the diameter is at most k k . We also extend this result from planar graphs to any minor-closed family F F not containing all apex graphs. In contrast, it is known to be NP-complete to decide whether a graph has an orientation such that the sum of all the shortest path lengths is at most an integer specified in the input. We give a simpler proof of this result.
graph orientation diameter planar graph apex graph graph minors