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

Abstract

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

How to cite

top

Mahdieh 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [14] B.D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998) 306-324, doi: 10.1006/jagm.1997.0898. Zbl0894.68107
  15. [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. [16] W.T. Tutte, A theory of 3-connected graphs, Nederl. Akad. Wetensch. Proc. (A) 64 (1961) 441-455. Zbl0101.40903

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.