A k-apex graph is a graph with a subset of k vertices, called apices, whose removal makes the graph planar. We present an O(k ^2 n \log^3 n )-time algorithm that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinksT, computes a maximum flow from S to T in G . This improves by a factor of k on the fastest algorithm previously known for this problem [   Borradaile et al., FOCS 2012, SICOMP 2017] . Our improvement is achieved by introducing a new variant of the push-relabel algorithm for computing maximum flows. We use our improved algorithm for maximum flow in  k-apex graphs , together with additional insights, to obtain an O(k^3 n \\textrm{polylog (nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of k^2 over the fastest algorithm previously known for this problem%DIFDELCMD < [%%% Wang, SODA 2019 .
We give an O(k ^3 n \polylog(nC) )-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks . This improves by a factor of k ^2 over the fastest algorithm previously known for this problem [ Wang, SODA 2019 . The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses k invocations of a maximum flow algorithm in a planar graph with k apices Borradaile et al., FOCS 2012, SICOMP 2017] , by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we introduce a new variant of the push-relabel algorithm of Goldberg and Tarjan and use it to find a maximum flow in the k-apex graphs \textrm{ %DIFDELCMD < [%%% that arise in Wang's procedure, faster than the algorithm of Borradaile et al .
R
A k-apex graph is a graph with a subset of k vertices, called apices, whose removal makes the graph planar. We present
We give
R
^2 n \log^3 n
^3 n \
A
polylog
A
(nC)
R
that, given a directed k-apex graph G with n vertices, arc capacities, a set of sources S and a set of sinksT, computes a maximum flow from S to T in G
for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks
R
on
^2 over
A
Wang, SODA 2019
A
. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses k invocations of a maximum flow algorithm in a planar graph with k apices
R
. Our improvement is achieved by introducing
, by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we introduce
R
for computing maximum flows. We use our improved algorithm for
of Goldberg and Tarjan and use it to find a
A
the
D
, together with additional insights, to obtain an O(k^3 n \
D
polylog
D
(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of k^2 over the fastest algorithm previously known for this problem
R
Wang, SODA 2019
that arise in Wang's procedure, faster than the algorithm of Borradaile et al