%0 Journal Article
%T Graphs with no Minor Containing a Fixed Edge
%A Donald K. Wagner
%J International Journal of Combinatorics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/783710
%X It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e, there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this paper generalizes this result to any nonplanar graph G provided G does not have a minor containing the given edge e. Ford and Fulkerson used their result to provide an efficient algorithm for solving the maximum-flow problem on planar graphs. As a corollary to the main result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs. 1. Introduction This paper examines the structure of paths and cuts in a graph relative to a fixed edge. In particular, let be a graph, and let be an edge of . Define an -path of to be a path such that is a cycle of . Define an -cut of to be a cut of that contains (in this paper, paths and cycles do not have repeated nodes and are equated with their edge sets. Also, cuts are minimal; i.e., no cut properly contains another.) Ford and Fulkerson [1] showed that if is planar, then there exists an -path that intersects every -cut in exactly one edge. This Ford-Fulkerson property does not hold for graphs in general. Specifically, take . Then, for any edge of and any -path , one can always find an -cut that intersects in more than one edge. The Ford-Fulkerson property, however, is not confined solely to planar graphs; in particular, if , then it is easy to find an -path, for any choice of , that intersects every -cut in exactly one edge. One of the main goals of this paper is to extend the Ford-Fulkerson result to a larger class of graphs. Motivated by the example above, it is shown that if is excluded in the proper way, then this goal can be achieved. Below is the main result of the paper. Throughout the paper, denotes the number of nodes of a graph, and the number of edges. Theorem 1. Let be a graph, and let be an edge of . If is connected, and does not have a minor containing , then there exists an -path of that intersects every -cut of in exactly one edge. Moreover, such an -path can be found in time. Theorem 1 is then used to provide a very simple -time algorithm for the maximum-flow problem for graphs in this class. This is within a logarithmic factor of the fastest maximum-flow algorithm, namely, the recent algorithm due to Orlin [2]. The remainder of the paper is outlined as follows. The next section introduces a graph decomposition, which serves as a key ingredient for the proof
%U http://www.hindawi.com/journals/ijcom/2013/783710/