Hasheminezhad, Mahdieh; McKay, Brendan; Reeves, Tristian
We describe for the first time how the 5-regular simple planar graphs can all be obtained from an elementary family of starting graphs by repeatedly applying a few local expansion operations. The proof uses an innovative amalgam of theory and computation. By incorporating the recursion into the canonical construction path method of isomorph rejection, a generator of non-isomorphic embedded 5-regular planar graphs is obtained with time complexity O(n 2) per isomorphism class.
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.