Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
DOI: 10.7155/jgaa.00232
Recursive generation of simple planar 5-regular graphs and pentangulations
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.
|
Submitted: May 2009.
Reviewed: January 2010.
Revised: April 2010.
Accepted: October 2010.
Final: November 2010.
Published: July 2011.
|
Journal Supporters
|