DIMACS TR: 93-60
Shortcutting Planar Digraphs
Author: Mikkel Thorup
ABSTRACT
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