b'@techreport{,'b'\nTITLE = {Reachability substitutes for planar digraphs},\nAUTHOR = {Katriel, Irit and Kutz, Martin and Skutella, Martin},\nLANGUAGE = {eng},\nURL = {http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2005-1-002},\nNUMBER = {MPI-I-2005-1-002},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {2005},\nDATE = {2005},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'