Some new results on three-terminal planar graph reducibility
Sofya Poger, A. Satyanarayana · 2001
This thesis focuses on the reducibility of 3-terminal planar graphs. Suppose G is a graph and T ⊂ V(G) is a specified set of nodes called terminals. Then G is said to be T-terminal delta-wye-delta reducible if G can be reduced to a graph H such that V(H) = T using a finite sequence of delta-wye-delta replacements. Akers conjectured that every planar graph is a 3-terminal delta-wye-delta reducible graph. Gitler proved that every grid graph, a restricted special case of planar graphs, is 3-terminal delta-wye-delta reducible and any minor of a grid graph is also a 3-terminal delta-wye-delta reducible graph. Akers conjecture follows from Gitler's result and the fact that every planar graph can be embedded in some grid graph. In this thesis we show that planar graph G is 3-terminal delta-wye-delta reducible by applying delta-wye-delta replacements directly on G itself, thus avoiding the problem of grid embeddings. The algorithm presented in this thesis requires O(| V(G)|2) delta-wye-delta operations to reduce G. The results presented in this thesis yield efficient reduction algorithms for 3-terminal undirected planar graphs thus opening the possibility to use delta-wye-delta replacements in solving a wide variety of problems. Among them are various enumeration problems including counting the number of spanning trees, multi-commodity flow problem, multi-terminal network reliability problems and many others.