Resource type
Thesis type
(Thesis) Ph.D.
Date created
2012-10-02
Authors/Contributors
Author: Demasi, Lino Merrit
Abstract
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.
Document
Identifier
etd7556
Copyright statement
Copyright is held by the author.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Mohar, Bojan
Member of collection
Download file | Size |
---|---|
etd7556_LDemasi.pdf | 1.17 MB |