On Terminal Delta-Wye Reducibility of Planar Graphs
We prove terminal Delta-Y reducibility of planar graphs with at most three terminals. The most important consequence of our proof is that this implicitly gives an efficient algorithm with time complexity O(vertical bar E(G)vertical bar(4)) for reducibility of planar graphs G with at most three terminals. It also can be used for restricted reducibility problems with more terminals. Our proof uses a very well-known translation from these operations to transformations on the medial graph. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 174-186 2011
planar graphs medial graph delta-wye transformations topological graph theory