Quartic Planar Graphs Jane Tan

Jane Tan's 2018 honours thesis in mathematics, on "Quartic Planar Graphs", supervised by Brendan McKay and Scott Morrison, is available here.


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 $P_5$-decomposition if and only if it has even order. Finally, we give some new smaller counterexamples to a disproven conjecture of Lovász 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.

last modified: 2018-11-19