SODA Conference 2015 Conference Paper
Four terminal planar Delta-Wye reducibility via rooted K 2, 4 minors
- Lino Demasi
- Bojan Mohar
A graph with four special vertices (called terminals) is wye-delta reducible if we can obtain a graph on four vertices by a sequence of wye-delta and delta-wye operations and series-parallel reductions, none of which is allowed to remove any of the terminals. A good characterization of wye-delta reducible 3-connected planar graphs with four terminals is given. The proofs yield an O ( n 2 ) time algorithm that either exhibits an obstruction to the 4-terminal reducibility or returns a sequence of wye-delta operations and series-parallel reductions that reduce the input graph to a subgraph of K 4 whose vertices are the terminals. We also discuss terminal wye-delta reducibility when a mixture of vertices and faces are treated as terminals. It is also shown that a sufficiently connected cubic graph is wye-delta reducible if and only if it does not contain the Petersen graph as a minor. The main ingredient in the proofs is a good characterization of planar graphs with four terminals that do not admit a rooted K 2, 4 minor with the four terminals corresponding to the roots on the large side of the bipartition of K 2, 4. Up to small connectivity reductions, cases without the rooted minor fall into five structural cases that lead to a polynomial-time algorithm for recognition of these graphs and construction of rooted K 2, 4 minors. This result is of independent interest in structural graph theory.