ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2021): 1.028

5-year Journal Impact Factor (2021): 0.934

CiteScore (2021): 1.7

SNIP (2021): 1.157

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 30(1) (2010) 123-136


Mahdieh Hasheminezhad

Department of Computer Science
Faculty of Mathematics and Computer Science
Amirkabir University of Technology, Tehran, Iran

Brendan D. McKay

School of Computer Science
Australian National University
ACT 0200, Australia


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.

2010 Mathematics Subject Classification: 05C10, 05C85.


[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 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 ~ 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_0006.
[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_12.
[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:3<223::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.

Received 25 June 2008
Revised 28 April 2009
Accepted 28 April 2009