Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes
Gunnar Brinkmann, Brendan D. McKay · ANU Open Research (Australian National University) · 2003
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.