Multicommodity flows in certain planar directed networks

For a class CB (capacity balanced networks) of directed planar networks, we give an O( K | V |) time graph theoretic algorithm for testing feasibility of the multicommodity flow problem, where K is the number of commodities and | V | is the number of nodes. A network in CB satisfies the following conditions: (1) The graph is directed, planar and acyclic. (2) All nodes without entering arcs and all nodes without outgoing arcs are located on the boundary of the outer face of the graph. (3) Each commodity has exactly one source and one sink, where the sink is located on the boundary. (4) Each node is capacity balanced. It is also shown that this class of networks has the integral flow property. Then we extend class CB to class CS (capacity semi-balanced networks) by relaxing condition (4), and show that CS can be reduced to CB. Therefore, CS also has a polynomial time graph theoretic algorithm and the integral flow property.