Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

Mahdieh Hasheminezhad; Brendan D. McKay

doi:10.7151/dmgt.1482

Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

Mahdieh Hasheminezhad^*, Brendan D. McKay

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.

Original language	English
Pages (from-to)	123-136
Number of pages	14
Journal	Discussiones Mathematicae - Graph Theory
Volume	30
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1482
Publication status	Published - 2010

Access to Document

10.7151/dmgt.1482

Cite this

@article{1ab4147fa82e4ba3bb214a022d340de8,

title = "Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4",

abstract = "We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.",

keywords = "Generation, Octahedrite, Planar graph, Quadrangulation",

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

year = "2010",

doi = "10.7151/dmgt.1482",

language = "English",

volume = "30",

pages = "123--136",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

AU - Hasheminezhad, Mahdieh

AU - McKay, Brendan D.

PY - 2010

Y1 - 2010

N2 - We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.

AB - We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.

KW - Generation

KW - Octahedrite

KW - Planar graph

KW - Quadrangulation

UR - https://www.scopus.com/pages/publications/77956534394

U2 - 10.7151/dmgt.1482

DO - 10.7151/dmgt.1482

M3 - Article

SN - 1234-3099

VL - 30

SP - 123

EP - 136

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 1

ER -

Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

Abstract

Access to Document

Other files and links

Fingerprint

Cite this