Computing Obstruction Sets

Abstract

This thesis focuses on extending the scope of practically computable obstruction sets. An obstruction set under a graph ordering <̲ for a family of graphs F is a characterisation of the family in terms of containment: a graph G is not in the family if and only if there is some obstruction H such that H <̲ G. The prototype is Kuratowski's Theorem. We describe how existing algorithms can be extended to compute obstruction sets under the immersion, Y - and H -orders, and other practical measures to improve the feasibility of computation. This allowed us to compute for the first time the minor order obstructions for graphs with vertex cover at most 7. We then briefly outline a simple finite state algorithm for a congruence for boundaried graphs embeddable in any orientable or nonorientable closed surface, possibly with a specified number of covering faces (generalising outer-planarity) or apex vertices. Having implemented (most of) this algorithm we can compute the complete obstruction sets for these graph families given a pathwidth bound on the obstructions. We currently have no such bounds, but demonstrate the method by computing partial obstruction sets for the plane, projective plane, Klein bottle, torus and double torus. We also provide a new, shorter proof that the minor order obstruction set of the union of two ideals C₁ and C₂ is computable from the obstruction sets for C₁ and C₂.