Brona Brejova, Tomas Vinar. Weihe's algorithm for maximum flow in planar graphs. Unpublished manuscript, University of Waterloo, December 1999.
Download preprint: 99weihe.ps, 632Kb
Download from publisher: not available
Related www page: 99weihe.zip
Bibliography entry: BibTeX
The maximum flow problem has been one of the most well-studied problems in algorithmic graph theory over the last 50 years. It has many important applications in many different areas. Also many modifications of the problem were studied. In this project we are interested in a special case of planar graphs. The first \$O(nlog n)\$ algorithm for general planar (directed) case was developed by Weihe in 1997. This algorithm is of our particular interest. The main goal of this project was to implement Weihe's algorithm. During the work on the project we have found several errors in the article. We have summarized errors and corrected them in the report. Also we have completely described algorithm for removing clockwise cycles in planar network. As far as we know this is the first such complete description. As a side effect of our work we have developed new algorithm for removing useless edges in general graphs working in \$O(mlog n)\$ time. As far as we know this is the first solution of this problem. The question whether there exists more efficient solution at least for planar graphs remains open. Finally, we have developed relatively simple method for implementing back transformation. Back transformation was not described in the original article at all. Our implementation is available in the file 99weihe.zip.
Last update: 10/01/2006