## 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