Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes
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.
|Collections||ANU Research Publications|
|Source:||MATCH - Communications in Mathematical and in Computer Chemistry|