Abstract. Flow in planar graphs has been extensively studied, and very efficient algorithms have been developed to compute max-flows, min-cuts, and circulations. Intimate connections between solutions to the planar circulation problem and with "consistent" potential functions in the dual graph are shown. It is also shown that the set of integral circulations in a planar graph very naturally forms a distributive lattice whose maximum corresponds to the shortest path tree in the dual graph. Further characterized is the lattice in terms of unidirectional cycles with respect to a particular face called the root face. It is shown how to compactly encode the entire lattice and it is also shown that the set of solutions to the min-cost flow problem forms a sublattice in the presented lattice.
Khuller, Naor, and Klein REF observed that the set of integral circulations in a planar graph form a distributive lattice, and solutions to the minimum cost circulation problem form a sublattice.
THE LATTICE STRUCTURE OF FLOW IN PLANAR GRAPHS
SIAM J. Discrete Math.
SIAM J. Discrete Math.
Mathematics Computer Science