Recursive generation of simple planar 5-regular graphs and pentangulations

Mahdieh Hasheminezhad*, Brendan D. McKay, Tristan Reeves

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    10 Citations (Scopus)

    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 languageEnglish
    Pages (from-to)417-436
    Number of pages20
    JournalJournal of Graph Algorithms and Applications
    Volume15
    Issue number3
    DOIs
    Publication statusPublished - 2011

    Fingerprint

    Dive into the research topics of 'Recursive generation of simple planar 5-regular graphs and pentangulations'. Together they form a unique fingerprint.

    Cite this