Skip navigation
Skip navigation

Recursive Generation of 5-Regular Planar Graphs

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.

CollectionsANU Research Publications
Date published: 2009
Type: Book chapter
DOI: 10.1007/978-3-642-00202-1_12


File Description SizeFormat Image
01_Hasheminezhad_Recursive_Generation_of_2009.pdf267.06 kBAdobe PDF    Request a copy
02_Hasheminezhad_Recursive_Generation_of_2009.pdf430.23 kBAdobe PDF    Request a copy
03_Hasheminezhad_Recursive_Generation_of_2009.pdf54.66 kBAdobe PDF    Request a copy
04_Hasheminezhad_Recursive_Generation_of_2009.pdf541.23 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator