Reachability substitutes for planar digraphs
Irit Katriel, Martin Kütz, Martin Skutella · MPG.PuRe (Max Planck Society) · 2005
Given a digraph $G = (V,E)$ with a set $U$ of vertices marked ``interesting,'' we want to find a smaller digraph $\\RS{} = (V',E')$ with $V' \\supseteq U$ in such a way that the reachabilities amongst those interesting vertices in $G$ and \\RS{} are the same. So with respect to the reachability relations within $U$, the digraph \\RS{} is a substitute for $G$. We show that while almost all graphs do not have reachability substitutes smaller than $\\Ohmega(|U|^2/\\log |U|)$, every planar graph has a reachability substitute of size $\\Oh(|U| \\log^2 |U|)$. Our result rests on two new structural results for planar dags, a separation procedure and a reachability theorem, which might be of independent interest.