DIMACS TR: 93-60

Shortcutting Planar Digraphs

Author: Mikkel Thorup


It is shown that given a planar digraph, by at most doubling the number of arcs but without changing the transitive closure, we can obtain a digraph such that whenever there is a dipath from one vertex to another there is such a dipath of length $O(\alpha(p,p)(\log p)^2)$, where $p$ is the number of vertices and $\alpha$ is a functional inverse of Ackermann's function.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-60.ps
DIMACS Home Page