Characterization and enumeration of toroidal K_3,3-subdivision-free graphs
<|reference_start|>Characterization and enumeration of toroidal K_3,3-subdivision-free graphs: 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)].<|reference_end|>
@article{gagarin2004characterization,
    title={Characterization and enumeration of toroidal K_{3,3}-subdivision-free
  graphs},
    author={Andrei Gagarin, Gilbert Labelle, Pierre Leroux (LaCIM, Universite du
  Quebec a Montreal)},
    journal={Discrete Math. 307 (2007), no. 23, pp. 2993-3005},
    year={2004},
    doi={10.1016/j.disc.2007.03.083},
    archivePrefix={arXiv},
    eprint={math/0411356},
    primaryClass={math.CO cs.DM}
}