A simple quadrangulation of the sphere is a finite simple graph embedded on the sphere such that every face is bounded by a walk of 4 edges. We consider the following classes of simple quadrangulations: arbitrary, minimum degree 3, 3-connected, and 3-connected without non-facial 4-cycles. In each case, we show how the class can be generated by starting with some basic graphs in the class and applying a sequence of local modifications. The duals of our algorithms generate classes of quartic (4-regular) planar graphs. In the case of minimum degree 3, our result is a strengthening of a theorem of Nakamoto and almost implicit in Nakamoto's proof. In the case of 3-connectivity, a corollary of our theorem matches a theorem of Batagelj. However, Batagelj's proof contained a serious error which cannot easily be corrected. We also give a theoretical enumeration of rooted planar quadrangulations of minimum degree 3, and some counts obtained by a program of Brinkmann and McKay that implements our algorithm. © 2005 Elsevier B.V. All rights reserved.

Generation of simple quadrangulations of the sphere / Gunnar, Brinkmann; Sam, Greenberg; Catherine, Greenhill; Brendan D., Mckay; R., Thomas; Wollan, PAUL JOSEPH. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 305:1-3(2005), pp. 33-54. [10.1016/j.disc.2005.10.005]

Generation of simple quadrangulations of the sphere

WOLLAN, PAUL JOSEPH
2005

Abstract

A simple quadrangulation of the sphere is a finite simple graph embedded on the sphere such that every face is bounded by a walk of 4 edges. We consider the following classes of simple quadrangulations: arbitrary, minimum degree 3, 3-connected, and 3-connected without non-facial 4-cycles. In each case, we show how the class can be generated by starting with some basic graphs in the class and applying a sequence of local modifications. The duals of our algorithms generate classes of quartic (4-regular) planar graphs. In the case of minimum degree 3, our result is a strengthening of a theorem of Nakamoto and almost implicit in Nakamoto's proof. In the case of 3-connectivity, a corollary of our theorem matches a theorem of Batagelj. However, Batagelj's proof contained a serious error which cannot easily be corrected. We also give a theoretical enumeration of rooted planar quadrangulations of minimum degree 3, and some counts obtained by a program of Brinkmann and McKay that implements our algorithm. © 2005 Elsevier B.V. All rights reserved.
2005
graph; map; planar; quadrangulation; quartic
01 Pubblicazione su rivista::01a Articolo in rivista
Generation of simple quadrangulations of the sphere / Gunnar, Brinkmann; Sam, Greenberg; Catherine, Greenhill; Brendan D., Mckay; R., Thomas; Wollan, PAUL JOSEPH. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - 305:1-3(2005), pp. 33-54. [10.1016/j.disc.2005.10.005]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/443296
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 63
  • ???jsp.display-item.citation.isi??? 56
social impact