Directed graphs requiring large numbers of shortcuts
William Hesse · 2003
A conjecture by Thorup is that the diameter of a directed graph with n vertices and m edges can be reduced to (log n) in by adding O(m) edges [3]. We give a counterexample to this conjecture. We construct a graph G requiring the addition of # mn ) edges to reduce its diameter below #(n ). By extending the construction to higher dimensions, we construct graphs with n edges that require the addition of # n ) edges to reduce their diameter.