Flows in One-Crossing-Minor-Free Graphs

Authors

  • Erin Wolf Chambers
  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00291

Keywords:

maximum flows , minor free graphs , flow algorithms , 1-crossing minor free graphs

Abstract

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(nlogn) time. In particular, maximum flows in directed K3,3-minor-free graphs and directed K5-minor-free graphs can be computed in O(nlogn) time without additional assumptions.

Downloads

Download data is not yet available.

Downloads

Published

2013-03-01

How to Cite

Chambers, E. W., & Eppstein, D. (2013). Flows in One-Crossing-Minor-Free Graphs. Journal of Graph Algorithms and Applications, 17(3), 201–220. https://doi.org/10.7155/jgaa.00291

Issue

Section

Articles

Categories