Eulerian digraph immersion
Paul D. Seymour, Carl Darwin Thor Johnson · Princeton University eBooks · 2002
The Graph Minors series of Robertson and Seymour has produced many deep results with wide ranging application. These include the general structure theorem for graphs with a forbidden minor, a positive resolution of Wagner's well-quasi-ordering conjecture, and polynomial time algorithms for important classes of problems on graphs. Of these, the structure theorem is the most fundamental. This thesis proves a similar theorem for the class of 4-regular eulerian digraphs (digraphs with in-degree and out-degree equal to two at every vertex). In a sense that will be made precise, a 4-regular eulerian digraph D that does not contain a fixed 4-regular eulerian digraph H embeds with high representativity, up to a bounded number of switches and vortices, on a surface on which H does not embed.