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

Mahdieh Hasheminezhad; Brendan D. McKay

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 1, page 123-136
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMahdieh Hasheminezhad, and Brendan D. McKay. "Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4." Discussiones Mathematicae Graph Theory 30.1 (2010): 123-136. <http://eudml.org/doc/270846>.

@article{MahdiehHasheminezhad2010,

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.},

author = {Mahdieh Hasheminezhad, Brendan D. McKay},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {planar graph; octahedrite; quadrangulation; generation},

language = {eng},

number = {1},

pages = {123-136},

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

url = {http://eudml.org/doc/270846},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Mahdieh Hasheminezhad

AU - Brendan D. McKay

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

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 1

SP - 123

EP - 136

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.

LA - eng

KW - planar graph; octahedrite; quadrangulation; generation

UR - http://eudml.org/doc/270846

ER -

## References

top- [1] V. Batagelj, An improved inductive definition of two restricted classes of triangulations of the plane, in: Combinatorics and Graph Theory, Banach Center Publications, 25 (PWN (Polish Scientific Publishers) Warsaw, 1989) 11-18. Zbl0742.05033
- [2] G. Brinkmann and A.W.M. Dress, A constructive enumeration of fullerenes, J. Algorithms 23 (1997) 345-358. Program at http://cs.anu.edu.au/ bdm/plantri, doi: 10.1006/jagm.1996.0806.
- [3] G. Brinkmann, S. Greenberg, C. Greenhill, B.D. McKay, R. Thomas and P. Wollan, Generation of simple quadrangulations of the sphere, Discrete Math. 305 (2005) 33-54, doi: 10.1016/j.disc.2005.10.005. Zbl1078.05023
- [4] G. Brinkmann, T. Harmuth and O. Heidemeier, The construction of cubic and quartic planar maps with prescribed face degrees, Discrete App. Math. 128 (2003) 541-554, doi: 10.1016/S0166-218X(02)00549-8. Zbl1018.05047
- [5] G. Brinkmann, and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007) 323-357; Program at http://cs.anu.edu.au/~bdm/plantri. Zbl1164.68025
- [6] G. Brinkmann and B.D. McKay, Construction of planar triangulations with minimum degree 5, Discrete Math. 301 (2005) 147-163, doi: 10.1016/j.disc.2005.06.019. Zbl1078.05022
- [7] H.J. Broersma, A.J.W. Duijvestijn and F. Göbel, Generating all 3-connected 4-regular planar graphs from the octahedron graph, J. Graph Theory 17 (1993) 613-620, doi: 10.1002/jgt.3190170508. Zbl0781.05047
- [8] J.W. Butler, A generation procedure for the simple 3-polytopes with cyclically 5-connected graphs, Canad. J. Math. 26 (1974) 686-708, doi: 10.4153/CJM-1974-065-6. Zbl0253.05111
- [9] M. Deza, M. Dutour and M. Shtogrin, 4-valent plane graphs with 2-, 3- and 4-gonal faces, in: Advances in Algebra and Related Topics, World Sci. Publ. (River Edge, NJ, 2003) 73-97, doi: 10.1142/9789812705808₀006.
- [10] M. Deza and M. Shtogrin, Octahedrites, Polyhedra, Symmetry: Culture and Science, The Quarterly of the International Society for the Interdisciplinary Study of Symmetry 11 (2000) 27-64.
- [11] M. Hasheminezhad, H. Fleischner and B.D. McKay, A universal set of growth operations for fullerenes, Chem. Phys. Lett. 464 (2008) 118-121, doi: 10.1016/j.cplett.2008.09.005.
- [12] M. Hasheminezhad, B.D. McKay and T. Reeves, Recursive generation of 5-regular planar graphs, Lecture Notes Comp. Sci. 5431 (2009) 345-356, doi: 10.1007/978-3-642-00202-1₁2. Zbl1211.05164
- [13] J. Lehel, Generating all 4-regular planar graphs from the graph of the octahedron, J. Graph Theory 5 (1981) 423-426, doi: 10.1002/jgt.3190050412. Zbl0474.05058
- [14] B.D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998) 306-324, doi: 10.1006/jagm.1997.0898. Zbl0894.68107
- [15] A. Nakamoto, Generating quadrangulations of surfaces with minimum degree at least 3, J. Graph Theory 30 (1999) 223-234, doi: 10.1002/(SICI)1097-0118(199903)30:3<223::AID-JGT7>3.0.CO;2-M Zbl0924.05018
- [16] W.T. Tutte, A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. (A) 64 (1961) 441-455. Zbl0101.40903

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.