On two dual classes of planar graphs

A planar graph G is delta-wye "Δ-Y" reducible if G can be reduced to an edge by a sequence of Δ-Y, series, parallel and degree-1 reductions. Politof characterizes Δ-Y reducible graphs in terms of forbidden homeomorphic subgraphs. A wye-delta "Y-Δ" reducible graph is one that can be reduced to an edge by a sequence of Y-Δ, series, parallel and degree-1 reductions. Y-Δ reducible graphs are all partial 3-trees. Recently, Arnborg and Proskurowski have shown confluent reductions which are both necessary and sufficient for the recognition of partial 3-trees. In this paper we note that Δ-Y graphs are the planar duals of Y-Δ graphs. We exploit this duality and the known reduction rules for partial 3-trees to characterize both classes of graphs using forbidden minors. The result yields a shorter proof of Politof's result. In addition, we give linear time algorithms for recognizing such graphs and for embedding any Δ-Y graph in a 4-tree. These algorithms complement many known linear time algorithms for solving some hard network problems on graphs given their embedding in a k-tree for some fixed k.