MPI-I-2005-1-002
Reachability substitutes for planar digraphs
Katriel, Irit and Kutz, Martin and Skutella, Martin
March 2005, 24 pages.
.
Status: available - back from printing
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.
-
- Attachement: MPI-I-2005-1-002.ps (327 KBytes); MPI-I-2005-1-002.pdf (303 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2005-1-002
BibTeX
@TECHREPORT{KatrielKutzSkutella2005,
AUTHOR = {Katriel, Irit and Kutz, Martin and Skutella, Martin},
TITLE = {Reachability substitutes for planar digraphs},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-2005-1-002},
MONTH = {March},
YEAR = {2005},
ISSN = {0946-011X},
}