Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs

Abstract

A simple, O(|V| 2 ) time algorithm is presented that reduces a connected two-terminal, undirected, planar graph to a single edge, by way of series and parallel reductions and delta-wye transformations. The method is applied to a class of optimization/equilibnum problems which includes max flow, shortest path, and electrical resistance problems.