Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4
Mahdieh Hasheminezhad ; Brendan D. McKay
Discussiones Mathematicae Graph Theory, Tome 30 (2010), p. 123-136 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2010-01-01
EUDML-ID : urn:eudml:doc:270846 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1482,
     author = {Mahdieh Hasheminezhad and Brendan D. McKay},
     title = {Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {30},
     year = {2010},
     pages = {123-136},
     zbl = {1214.05012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1482}
}

Mahdieh Hasheminezhad; Brendan D. McKay. Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 123-136. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1482/

[000] [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. | Zbl 0742.05033

[001] [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.

[002] [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. | Zbl 1078.05023

[003] [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. | Zbl 1018.05047

[004] [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. | Zbl 1164.68025

[005] [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. | Zbl 1078.05022

[006] [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. | Zbl 0781.05047

[007] [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. | Zbl 0253.05111

[008] [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.

[009] [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.

[010] [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.

[011] [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. | Zbl 1211.05164

[012] [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. | Zbl 0474.05058

[013] [14] B.D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998) 306-324, doi: 10.1006/jagm.1997.0898. | Zbl 0894.68107

[014] [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 | Zbl 0924.05018

[015] [16] W.T. Tutte, A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. (A) 64 (1961) 441-455. | Zbl 0101.40903