Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.