Recursive generation of 5-regular

Mahdieh Hasheminezhad; Brendan D. McKay; Tristan Reeves

doi:10.1007/978-3-642-00202-1_12

Recursive generation of 5-regular

Mahdieh Hasheminezhad^*, Brendan D. McKay, Tristan Reeves

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 ²) per isomorphism class.

Original language	English
Title of host publication	WALCOM
Subtitle of host publication	Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings
Pages	129-140
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-00202-1_12
Publication status	Published - 2009
Event	3rd International Workshop on Algorithms and Computation, WALCOM 2009 - Kolkata, India Duration: 18 Feb 2009 → 20 Feb 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5431 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Workshop on Algorithms and Computation, WALCOM 2009
Country/Territory	India
City	Kolkata
Period	18/02/09 → 20/02/09

Access to Document

10.1007/978-3-642-00202-1_12

Cite this

Hasheminezhad, M., McKay, B. D., & Reeves, T. (2009). Recursive generation of 5-regular. In WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings (pp. 129-140). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5431 LNCS). https://doi.org/10.1007/978-3-642-00202-1_12

@inproceedings{4b164b1f23d64c719a13fabbf207105a,

title = "Recursive generation of 5-regular",

abstract = "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.",

keywords = "5-regular, 5-valent, Graph, Map, Pentangulation, Planar, Quintic",

author = "Mahdieh Hasheminezhad and McKay, {Brendan D.} and Tristan Reeves",

year = "2009",

doi = "10.1007/978-3-642-00202-1_12",

language = "English",

isbn = "3642002013",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "129--140",

booktitle = "WALCOM",

note = "3rd International Workshop on Algorithms and Computation, WALCOM 2009 ; Conference date: 18-02-2009 Through 20-02-2009",

}

Hasheminezhad, M, McKay, BD & Reeves, T 2009, Recursive generation of 5-regular. in WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5431 LNCS, pp. 129-140, 3rd International Workshop on Algorithms and Computation, WALCOM 2009, Kolkata, India, 18/02/09. https://doi.org/10.1007/978-3-642-00202-1_12

Recursive generation of 5-regular. / Hasheminezhad, Mahdieh; McKay, Brendan D.; Reeves, Tristan.
WALCOM: Algorithms and Computation - Third International Workshop, WALCOM 2009, Proceedings. 2009. p. 129-140 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5431 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Recursive generation of 5-regular

AU - Hasheminezhad, Mahdieh

AU - McKay, Brendan D.

AU - Reeves, Tristan

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - 5-regular

KW - 5-valent

KW - Graph

KW - Map

KW - Pentangulation

KW - Planar

KW - Quintic

UR - http://www.scopus.com/inward/record.url?scp=67650504405&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-00202-1_12

DO - 10.1007/978-3-642-00202-1_12

M3 - Conference contribution

SN - 3642002013

SN - 9783642002014

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 129

EP - 140

BT - WALCOM

T2 - 3rd International Workshop on Algorithms and Computation, WALCOM 2009

Y2 - 18 February 2009 through 20 February 2009

ER -

Recursive generation of 5-regular

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this