Partition of planar flow networks

1 November 1983

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 259-264
https://doi.org/10.1109/sfcs.1983.44

Abstract

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).

Keywords

This publication has 7 references indexed in Scilit:

Maximum flow in (s,t) planar networks
Information Processing Letters, 1981
A data structure for dynamic trees
Published by Association for Computing Machinery (ACM) ,1981
Exploring binary trees and other simple trees
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1980
Maximum Flow in Planar Networks
SIAM Journal on Computing, 1979
A Separator Theorem for Planar Graphs
SIAM Journal on Applied Mathematics, 1979
Generalized Nested Dissection
SIAM Journal on Numerical Analysis, 1979
On the enumeration of planar maps
Bulletin of the American Mathematical Society, 1968