Quartic planar graphs

Abstract

In this thesis, we explore three problems concerning quartic planar graphs. The First is on recursive structures

we prove generation theorems for several interesting subclasses of quartic planar graphs and their duals, building on previous work which has largely been focussed on the simple or nonplanar cases. The second problem is on the existence of locally self-avoiding Eulerian circuits. As an application of a generation theorem, we prove that all but one 3-connected quartic planar graphs have an Eulerian circuit that is free of subcycles of length 3 or 4. This implies that a 3-connected quartic planar graph admits a P5-decomposition if and only if it has even order. Finally, we give some new smaller counterexamples to a disproven conjecture of Lovasz on circle representations of quartic planar graphs. We also present a gluing construction that tells us a little more about the obstructions to circle representability, although a full characterisation remains elusive.