TY - JOUR AU - Wagner, Donald PY - 2008/03/25 Y2 - 2024/03/29 TI - K3,3 Minors and the Maximum-Flow Problem JF - Algorithmic Operations Research JA - AOR VL - 3 IS - 1 SE - Articles DO - UR - https://journals.lib.unb.ca/index.php/AOR/article/view/4176 SP - AB - Let G be a graph, and let e be an edge of G. The main result of this paper is that any instance of the maximum-flow problem on G having e as the "return" edge can be solved in linear time provided G does not have a K<sub>3,3</sub> minor containing e. The primary tool in proving this result is a new graph decomposition. In particular, it is shown that if G is 3-connected and does not have a K<sub>3,3</sub> minor containing e, then it can be decomposed into planar graphs, "almost" planar graphs, and copies of K<sub>5</sub>. ER -