Geodesic
Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4
Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 1, pp. 123-136.

Voir la notice de l'article provenant de la source Library of Science

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: planar graph, octahedrite, quadrangulation, generation 
@article{DMGT_2010_30_1_a10,
     author = {Hasheminezhad, Mahdieh and McKay, Brendan},
     title = {Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {123--136},
     publisher = {mathdoc},
     volume = {30},
     number = {1},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a10/}
}
TY  - JOUR
AU  - Hasheminezhad, Mahdieh
AU  - McKay, Brendan
TI  - Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2010
SP  - 123
EP  - 136
VL  - 30
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a10/
LA  - en
ID  - DMGT_2010_30_1_a10
ER  - 
%0 Journal Article
%A Hasheminezhad, Mahdieh
%A McKay, Brendan
%T Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4
%J Discussiones Mathematicae. Graph Theory
%D 2010
%P 123-136
%V 30
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a10/
%G en
%F DMGT_2010_30_1_a10
Hasheminezhad, Mahdieh; McKay, Brendan. Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4. Discussiones Mathematicae. Graph Theory, Tome 30 (2010) no. 1, pp. 123-136. http://geodesic.mathdoc.fr/item/DMGT_2010_30_1_a10/

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

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

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

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

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

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

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

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

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

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

[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:3223::AID-JGT7>3.0.CO;2-M

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