1983 · 17 citations · 8 references
ComputingComputer ScienceCombinatoricsComputational GeometryComputer NetworksGraph TheoryNetwork Flow AlgorithmsNetwork FlowsDirected NetworksFlow NetworksMaximum FlowMaximum Flow AlgorithmsMaximum Flow ProblemsNetwork Flow ProblemsPlanar Graph AlgorithmsPlanar Network Flows
We give a new characterization of the planar separator theorem in terms of mutually non-containing closed Jordan Curves. using this, we develop an O(n √n logn) maximum flow algorithm for directed planar networks (hence for any planar network).
8
A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Applied Mathematics · 1979 · 1.4K citations
Richard J. Lipton, Donald J. Rose, Robert E. Tarjan · SIAM Journal on Numerical Analysis · 1979 · 560 citations
On the enumeration of planar maps
W. T. Tutte · Bulletin of the American Mathematical Society · 1968 · 181 citations · Full text
Maximum Flow in Planar Networks
Alon Itai, Yossi Shiloach · SIAM Journal on Computing · 1979 · 123 citations
A data structure for dynamic trees
Daniel D. Sleator, Robert E. Tarjan · 1981 · 110 citations