The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses \(O(k)\) invocations of an \(O(k^3 n \log^3 n)\)-time algorithm for 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 show two alternatives for computing flows in the \(k\)-apex graphs that arise in our
modification of Wang's procedure faster than the algorithm of Borradaile et al.
In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance
push-relabel algorithm of Goldberg and Tarjan [JACM 1988].