Vol 3 No 1 (2008)
Articles

K3,3 Minors and the Maximum-Flow Problem

Donald Wagner
Office of Naval Research, Arlington, VA 22203, USA
Published March 25, 2008
Keywords
  • maximum-flow problem,
  • planar graphs,
  • graph decomposition
How to Cite
Wagner, D. (2008). K3,3 Minors and the Maximum-Flow Problem. Algorithmic Operations Research, 3(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/4176

Abstract

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 K3,3 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 K3,3 minor containing e, then it can be decomposed into planar graphs, "almost" planar graphs, and copies of K5.