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(nlog n)$-time algorithm of Weihe [FOCS94 & JCSS97] for computing maximum $s,t$-flow in directed planar graphs. Previously, Weihes algorithm could not run in $O(nlog n)$-time due to the absence of the preprocessing step; all the preceding algorithms run in $tilde{Omega}(n^2)$-time [Misiolek-Chen, COCOON05 & IPL06; Biedl, Brejov{{a}} and Vinar, MFCS00]. Consequently, this provides an alternative $O(nlog n)$-time algorithm for computing maximum $s,t$-flow in directed planar graphs in addition to the known $O(nlog n)$-time algorithms [Borradaile-Klein, SODA06 & J.ACM09; Erickson, SODA10]. 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.
Download