Skip navigation
Skip navigation

Recursive generation of simple planar 5-regular graphs and pentangulations

Hasheminezhad, Mahdieh; McKay, Brendan; Reeves, Tristan

Description

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...[Show more]

CollectionsANU Research Publications
Date published: 2011
Type: Journal article
URI: http://hdl.handle.net/1885/59153
Source: Journal of Graph Algorithms and Applications
DOI: 10.7155/jgaa.00232

Download

File Description SizeFormat Image
01_Hasheminezhad_Recursive_generation_of_simple_2011.pdf531.88 kBAdobe PDF    Request a copy


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

Updated:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator