We study the maximum flow problem in directed H -minor-free graphs where H can be drawn in the plane with one crossing. If a structural decomposition of the graph as a clique-sum of planar graphs and graphs of constant complexity is given, we show that a maximum flow can be computed in O ( n log n ) time. In particular, maximum flows in directed K 3,3-minor-free graphs and directed K 5-minor-free graphs can be computed in O ( n log n ) time without additional assumptions.
展开▼
