Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00232 Recursive generation of simple planar 5-regular graphs and pentangulations Mahdieh Hasheminezhad , Brendan D. McKay , and Tristan Reeves Vol. 15, no. 3, pp. 417-436, 2011. Regular paper Abstract We describe 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 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(n2) per isomorphism class. A similar result is obtained for simple planar pentangulations with minimum degree 2.
|
Reviewed: January 2010. Final: November 2010. Published: July 2011. Revised: April 2010. Submitted: May 2009. Accepted: October 2010. Communicated by Sandip Das and Ryuhei Uehara |
Journal of Graph Algorithms and Applications |