Delta-Wye Transformations and the Efficient Reduction of Almost-Planar Graphs

A non-planar graph G is almost-planar if, for every edge e of G, either G\e or G/e is planar. We provide an algorithmic proof of a theorem by D. K. Wagner, according to which every almost-planar graph can be reduced to the graph K3,3 by some sequence of series/parallel reductions and delta-wye exchanges such that the reduction sequence is formed by almost-planar graphs. We study 3-connected almost-planar graphs on the projective plane and establish duality relations between the resulting families. We show that one family reduces to K3,3 (with an added parallel edge) while the dual family reduces to K5. We also characterize 3-terminal delta-wye reducibility for almost-planar graphs.