非表示:
キーワード:
-
要旨:
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.
