Abstrakt. Flöde i plana grafer har studerats ingående, och mycket effektiva algoritmer har utvecklats för att beräkna max-flöden, min-cuts och cirkulationer. Intima kopplingar mellan lösningar till de planara cirkulationsproblemen och med "konsistenta" potentiella funktioner i den dubbla grafen visas. Det visas också att uppsättningen av integrerade cirkulationer i en planar graf mycket naturligt bildar en distributiv lattice vars maximala motsvarar den kortaste vägen träd i den dubbla grafen. Ytterligare karakteriseras lattice i termer av enkelriktade cykler med avseende på ett särskilt ansikte som kallas roten ansikte. Det visas hur man kompakt kodar hela lattice och det visas också att uppsättningen av lösningar på min-kostnads flöde problem bildar en sublattice i den presenterade lattice.
Khuller, Naor och Klein REF konstaterade att uppsättningen integrerade cirkulationer i en planar graf bildar en distributiv lattice, och lösningar till den minsta kostnaden cirkulationsproblem bildar en sublattice.
THE LATTICE STRUCTURE OF FLOW IN PLANAR GRAPHS
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}