PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 1 | 123-136
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
30
Numer
1
Strony
123-136
Opis fizyczny
Daty
wydano
2010
otrzymano
2008-06-25
poprawiono
2009-04-28
zaakceptowano
2009-04-28
Twórcy
  • Department of Computer Science, Faculty of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
  • School of Computer Science, Australian National University, ACT 0200, Australia
Bibliografia
  • [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: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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1482
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.