{
  "id": "math/0411356",
  "version": "v1",
  "published": "2004-11-16T20:56:19.000Z",
  "updated": "2004-11-16T20:56:19.000Z",
  "title": "Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs",
  "authors": [
    "Andrei Gagarin",
    "Gilbert Labelle",
    "Pierre Leroux"
  ],
  "comment": "18 pages, 7 figures and 4 tables",
  "journal": "Discrete Math. 307 (2007), no. 23, pp. 2993-3005",
  "doi": "10.1016/j.disc.2007.03.083",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We describe the structure of 2-connected non-planar toroidal graphs with no K_{3,3}-subdivisions, using an appropriate substitution of planar networks into the edges of certain graphs called toroidal cores. The structural result is based on a refinement of the algorithmic results for graphs containing a fixed K_5-subdivision in [A. Gagarin and W. Kocay, \"Embedding graphs containing K_5-subdivisions'', Ars Combin. 64 (2002), 33-49]. It allows to recognize these graphs in linear-time and makes possible to enumerate labelled 2-connected toroidal graphs containing no K_{3,3}-subdivisions and having minimum vertex degree two or three by using an approach similar to [A. Gagarin, G. Labelle, and P. Leroux, \"Counting labelled projective-planar graphs without a K_{3,3}-subdivision\", submitted, arXiv:math.CO/0406140, (2004)].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-11-16T20:56:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "05C10",
      "68R10"
    ],
    "keywords": [
      "characterization",
      "enumeration",
      "graphs containing",
      "non-planar toroidal graphs",
      "minimum vertex degree"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math.....11356G"
    }
  }
}