Skip navigation
Skip navigation
A change is coming. Click to see a sneak peek of the new Open Research Repository.

Recursive Generation of 5-Regular Planar Graphs

Download (267.06 kB)

link to publisher version

  • Altmetric Citations

Hasheminezhad, Mahdieh; McKay, Brendan; Reeves, Tristian

Description

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.

dc.contributor.authorHasheminezhad, Mahdieh
dc.contributor.authorMcKay, Brendan
dc.contributor.authorReeves, Tristian
dc.date.accessioned2015-12-10T22:23:09Z
dc.identifier.isbn9783642002014
dc.identifier.urihttp://hdl.handle.net/1885/52657
dc.description.abstractWe 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.
dc.publisherSpringer
dc.relation.ispartofWALCOM: Algorithms and Computation
dc.subjectKeywords: 5-regular; 5-valent; Graph; Pentangulation; Planar; Quintic; Set theory; Computation theory 5-regular; 5-valent; Graph; Map; Pentangulation; Planar; Quintic
dc.titleRecursive Generation of 5-Regular Planar Graphs
dc.typeBook chapter
local.description.notesImported from ARIES
dc.date.issued2009
local.identifier.absfor080202 - Applied Discrete Mathematics
local.identifier.ariespublicationu3594520xPUB252
local.type.statusPublished Version
local.contributor.affiliationHasheminezhad, Mahdieh, Amirkabir University of Technology
local.contributor.affiliationMcKay, Brendan, College of Engineering and Computer Science, ANU
local.contributor.affiliationReeves, Tristian, Polytopia Systems Pty Ltd
local.description.embargo2037-12-31
local.bibliographicCitation.startpage129
local.bibliographicCitation.lastpage140
local.identifier.doi10.1007/978-3-642-00202-1_12
dc.date.updated2016-02-24T10:17:32Z
local.bibliographicCitation.placeofpublicationNew York
local.identifier.scopusID2-s2.0-67650504405
CollectionsANU Research Publications

Show simple item record


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

Updated:  17 November 2022/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator