Skip navigation
Skip navigation

Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes

Brinkmann, Gunnar; McKay, Brendan


We describe two algorithms for the construction of simple planar cubic 3-connected graphs with all face sizes in some specified set; equivalently, simple triangulations of the plane with all vertex degrees in a specified set. Output of non-isomorphic graphs is achieved without explicit isomorphism testing. We also give some results obtained using the algorithms, including the numbers of fullerenes up to 200 vertices, and verification of a famous conjecture of Barnette up to 250 vertices.

CollectionsANU Research Publications
Date published: 2003
Type: Journal article
Source: MATCH - Communications in Mathematical and in Computer Chemistry


There are no files associated with this item.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator