Computational Graph Theory

Pettersson, William (2014). Computational Graph Theory PhD Thesis, School of Mathematics and Physics, The University of Queensland. doi:10.14264/uql.2014.450

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s4117552_phd_submission.pdf Thesis (open access) application/pdf 1.20MB 0
Author Pettersson, William
Thesis Title Computational Graph Theory
School, Centre or Institute School of Mathematics and Physics
Institution The University of Queensland
DOI 10.14264/uql.2014.450
Publication date 2014-10-17
Thesis type PhD Thesis
Open Access Status Other
Supervisor Darryn Bryant
Benjamin A. Burton
Barbara Maenhaut
Total pages 254
Language eng
Subjects 0101 Pure Mathematics
Formatted abstract
This thesis involves the application of computational techniques to various problems in graph theory and low dimensional topology. The first two chapters of this thesis focus on problems in graph theory itself; in particular on graph decomposition problems. The last three chapters look at applications of graph theory to combinatorial topology, focusing on the exhaustive generation of certain families of 3-manifold triangulations.

Chapter 1 shows that the obvious necessary conditions are sufficient for the existence of a decomposition of the complete graph into cycles of arbitrary specified lengths. This problem was formally posed in 1981 by Brian Alspach, but has its origins in the mid 1800s. A complete discussion of problem, as well as a full solution, is presented in Chapter 1. This work has been published, see [33].

Chapter 2 solves a problem closely related to the Oberwolfach Problem, which was originally posed by Gerhard Ringel at a graph theory conference in Oberwolfach in 1967. We show that if a complete multipartite graph K has even degree, and F is a bipartite two factor of K, then there exists a factorisation of K into F (with the exception that there is no factorisation of the 6-regular complete bipartite graph into the 2-factor consisting of two 6-cycles). This work has been published, see [26]. The latter chapters of this thesis deal with the use of graph theory in combinatorial topology; in particular combinatorial 3-manifold topology.

Chapter 3 gives an introduction to the field of combinatorial topology, especially to the graph theoretic structures required for this thesis. Chapter 3 also gives an overview of the census enumeration problem, which we focus on for the last two chapters, and outlines an existing state-of-the-art algorithm for this problem.

In Chapter 4 we look at face pairing graphs of 3-manifold triangulations. When enumerating a census of triangulations, one often starts with a potential face pairing graph and attempts to flesh it out into a full 3-manifold triangulation. Computationally however, much time is spent on potential graphs which do not lead to any interesting triangulations. We show that determining whether such a graph will lead to a 3-manifold triangulation is fixed parameter tractable in the tree width of the graph. This work has been published, see [46].

In Chapter 5 we give a new census enumeration algorithm for 3-manifold triangulations. We use graph decompositions as the basis for this algorithm, which topologically is equivalent to identifying edges of tetrahedra together (as opposed to identifying faces together). We show that this algorithm complements existing state-of-the-art algorithms, potentially reducing census enumeration running times by a factor of two or more.
Keyword Graph theory
parameterised complexity

Document type: Thesis
Collections: UQ Theses (RHD) - Official
UQ Theses (RHD) - Open Access
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Fri, 10 Oct 2014, 00:22:41 EST by Mr William Pettersson on behalf of Scholarly Communication and Digitisation Service