Four-terminal reducibility and projective-planar wye-delta-wye-reducible graphs
Dan Archdeacon, Charles J. Colbourn, Isidoro Gitler, J. Scott Provan · Journal of Graph Theory · 2000
A graph is YΔY-reducible if it can be reduced to a vertex by a sequence of series-parallel reductions and YΔY-transformations. Terminals are distinguished vertices, that cannot be deleted by reductions and transformations. In this article, we show that four-terminal planar graphs are YΔY-reducible when at least three of the vertices lie on the same face. Using this result, we characterize YΔY-reducible projective-planar graphs. We also consider terminals in projective-planar graphs, and establish that graphs of crossing-number one are YΔY-reducible. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 83–93, 2000