Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes

Gunnar Brinkmann; Brendan D. McKay; Ulrike Von Nathusius

Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes

Gunnar Brinkmann^*, Brendan D. McKay, Ulrike Von Nathusius

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

Abstract

We describe two algorithms for the construction of simple planar cubic 3-connected graphs with all face sizes in some specified set; equivalently, simple triangulations of the plane with all vertex degrees in a specified set. Output of non-isomorphic graphs is achieved without explicit isomorphism testing. We also give some results obtained using the algorithms, including the numbers of fullerenes up to 200 vertices, and verification of a famous conjecture of Barnette up to 250 vertices.

Original language	English
Pages (from-to)	163-177
Number of pages	15
Journal	Match
Issue number	48
Publication status	Published - 2003

Cite this

@article{f28c6631939c4309a1213a390d0c2e40,

title = "Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes",

abstract = "We describe two algorithms for the construction of simple planar cubic 3-connected graphs with all face sizes in some specified set; equivalently, simple triangulations of the plane with all vertex degrees in a specified set. Output of non-isomorphic graphs is achieved without explicit isomorphism testing. We also give some results obtained using the algorithms, including the numbers of fullerenes up to 200 vertices, and verification of a famous conjecture of Barnette up to 250 vertices.",

author = "Gunnar Brinkmann and McKay, {Brendan D.} and {Von Nathusius}, Ulrike",

year = "2003",

language = "English",

pages = "163--177",

journal = "Match",

issn = "0340-6253",

publisher = "University of Kragujevac, Faculty of Science",

number = "48",

}

TY - JOUR

T1 - Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes

AU - Brinkmann, Gunnar

AU - McKay, Brendan D.

AU - Von Nathusius, Ulrike

PY - 2003

Y1 - 2003

N2 - We describe two algorithms for the construction of simple planar cubic 3-connected graphs with all face sizes in some specified set; equivalently, simple triangulations of the plane with all vertex degrees in a specified set. Output of non-isomorphic graphs is achieved without explicit isomorphism testing. We also give some results obtained using the algorithms, including the numbers of fullerenes up to 200 vertices, and verification of a famous conjecture of Barnette up to 250 vertices.

AB - We describe two algorithms for the construction of simple planar cubic 3-connected graphs with all face sizes in some specified set; equivalently, simple triangulations of the plane with all vertex degrees in a specified set. Output of non-isomorphic graphs is achieved without explicit isomorphism testing. We also give some results obtained using the algorithms, including the numbers of fullerenes up to 200 vertices, and verification of a famous conjecture of Barnette up to 250 vertices.

UR - http://www.scopus.com/inward/record.url?scp=0142169797&partnerID=8YFLogxK

M3 - Article

SN - 0340-6253

SP - 163

EP - 177

JO - Match

JF - Match

IS - 48

ER -

Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes

Abstract

Other files and links

Fingerprint

Cite this