  We present a linear-time algorithm for simplifying flow networks on directed
planar graphs: Given a directed planar graph on $n$ vertices, a source vertex
$s$ and a sink vertex $t$, our algorithm removes all the arcs that do not
participate in any simple $s,t$-path in linear-time. The output graph produced
by our algorithm satisfies the prerequisite needed by the $O(n\log n)$-time
algorithm of Weihe [FOCS'94 \& JCSS'97] for computing maximum $s,t$-flow in
directed planar graphs. Previously, Weihe's algorithm could not run in $O(n\log
n)$-time due to the absence of the preprocessing step; all the preceding
algorithms run in $\tilde{\Omega}(n^2)$-time [Misiolek-Chen, COCOON'05 \&
IPL'06; Biedl, Brejov{\'{a}} and Vinar, MFCS'00]. Consequently, this provides
an alternative $O(n\log n)$-time algorithm for computing maximum $s,t$-flow in
directed planar graphs in addition to the known $O(n\log n)$-time algorithms
[Borradaile-Klein, SODA'06 \& J.ACM'09; Erickson, SODA'10].
  Our algorithm can be seen as a (truly) linear-time $s,t$-flow sparsifier for
directed planar graphs, which runs faster than any maximum $s,t$-flow algorithm
(which can also be seen of as a sparsifier). The simplified structures of the
resulting graph might be useful in future developments of maximum $s,t$-flow
algorithms in both directed and undirected planar graphs.
