Directed graphs requiring large numbers of shortcuts

ABSTRACT

A conjecture by Thorup is that the diameter of a directed graph with n vertices and m edges can be reduced to (log n)^O(1) by adding O(m) edges [3]. We give a counterexample to this conjecture. We construct a graph G requiring the addition of Ω(mn ^1/17) edges to reduce its diameter below Θ(n^1/17). By extending the construction to higher dimensions, we construct graphs with n^1+ε edges that require the addition of Ω(n^2--ε) edges to reduce their diameter. These constructions yield time-space tradeoffs in lower bounds for transitive closure queries in a certain computational model.

REFERENCES

• 1: Antal Balog , Imre Bárány, On the convex hull of the integer points in a disc, Proceedings of the seventh annual symposium on Computational geometry, p.162-165, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109666]
• 2: Imre Bárány and David Larman. The convex hull of the integer points in a large ball. Mathematische Annalen, 312:167--181, 1998.
• 3: Mikkel Thorup, On Shortcutting Digraphs, Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science, p.205-211, June 19-20, 1992
• 4: M. Thorup. Shortcutting planar digraphs. Combinatorics, Probability, & Computing, 4:287--315, 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Theory