Rooted Minors and Delta-Wye Transformations

In this thesis, we study terminal minors and delta-wye reducibility. The concept of terminal minors extends the notion of graph minors to the case where we have a distinguished set of vertices $T$ in our graph $G$ that must correspond to a distinguished set of vertices $Y$ in the minor. Delta-wye reducibility concerns the study of how graphs can be reduced under a set of six operations: the four series-parallel reductions, delta-wye, and wye-delta transformations. For terminal minors, we completely characterize when, given a planar graph with four terminals, we can find a minor of $K_{2,4}$ in that graph with the four terminal vertices forming the larger part of the bipartition. This is an extension of a result due to Robertson and Seymour for the case when a graph contains three terminals. For delta-wye reducibility, we study the problem of reducibility for the class of graphs consisting of four-terminal planar graphs. Using the results about rooted $K_{2,4}$ minors, we are able to characterize when 3-connected graphs in this class are reducible.