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 construc- tion 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 pen- tangulations with minimum degree 2.
Original language | English |
---|---|
Pages (from-to) | 417-436 |
Number of pages | 20 |
Journal | Journal of Graph Algorithms and Applications |
Volume | 15 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2011 |