Obstructions to Graph and Digraph Embedding

Abstract

This thesis explores two independent problems, both of which aim to describe graph and directed graph (digraph) properties via sets of forbidden obstructions. Taking inspiration from Kuratowski’s Theorem for planar graphs, the first chapter investigates structural characterizations of strongly connected digraphs whose underlying undirected graphs contain specific subdivisions or minors. In particular, we discuss strongly connected digraphs which are outerplanar, series-parallel, planar, and which contain subdivisions or minors of various wheel graphs and the triangular prism graph. In the second chapter, we expand upon a theorem of Thomassen on acyclic digraphs embedded in the closed disc by proving a structural result on acyclic digraphs embedded in the closed annulus.