Graph immersions

One of the first prominent theorems in structural graph theory is the Kuratowski-Wagner theorem which characterizes planar graphs as those with no K_{3,3} or K_5 minor. Numerous other classical theorems give precise descriptions of the class of graphs with no H-minor for numerous small graphs H. In particular, such classifications exist when H is W_4, W_5, Prism, K_{3,3}, K_5, Octahedron, and Cube. One of the most useful tools in establishing such results are splitter theorems which reduce a graph while preserving both connectivity and containment of a given minor. In this thesis we consider analogous problems for a different containment relation: immersion. Although immersion is a standard containment relation, prior to this thesis there were almost no precise structure theorems for forbidden immersions. The most prominent theorems in this direction give a rough description of graphs with no W_4 immersion and those with no K_{3,3} or K_5 immersion. Our main contributions include precise structure theorems for the class of graphs with no H-immersion when H is one of K_4, W_4, Prism, and K_{3,3}. To assist in this exploration, we have also established two splitter theorems for graph immersions, one for 2k-edge-connected graphs, and another for 3-edge-connected and internally 4-edge-connected graphs.