Before revision: 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] .
After revision: We give 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] .