Enumeration of polyhedral graphs

This thesis is concerned with the design of a polyhedron enumeration algorithm. The approach taken focuses on specic classes of polyhedra and their graph theoretic properties. This is then compared more broadly to other graph enumeration algorithms that are concerned with the same or a superset which includes these properties. An original and novel algorithm is contributed to this area. The approach taken divides the problem into prescribed vertex and face degree sequences for the graphs. Using a range of existence, ordered enumeration and isomorphism techniques, it finds all unique 4-regular, 3-connected planar graphs. The algorithm is a vertex addition algorithm which means that each result output at a given stage has a new vertex added. Other results from different stages are never required for further computation and comparison, hence the process is embarrassingly parallel. Therefore, the enumeration can be distributed optimally across a cluster of computers. This work has led to a successfully implemented algorithm which takes a different approach to its treatment of the class of 4-regular, 3-connected planar graphs. As such this has led to observations and theory about other classes of graphs and graph embeddings which relate to this research.

Grantor dc:publisher

Oxford Brookes University

Year dc:date

2019

Author dc:creator

• Kamperis, Samuel G.

Contributors dc:contributor

• Long, Rachel
• Hayatleh, Khaled

Statement dc:rights

• All rights reserved

Language dc:language

en

DOI dc:identifier

https://doi.org/10.24384/qctn-w863

OAI identifier oai:identifier

tle:6dccadc1-e203-40ea-9932-3de0ce0f7a58:d6bd9758-527a-46cd-bfe2-c433766e8fca:1