The structure of K3,3K3,3-subdivision-free toroidal graphs

We consider the class TT of 2-connected non-planar K3,3K3,3-subdivision-free graphs that are embeddable in the torus. We show that any graph in TT admits a unique decomposition as a basic toroidal graph (the toroidal core  ) where the edges are replaced by two-pole networks constructed from 2-connected planar graphs. The structure theorem provides a practical algorithm to recognize toroidal graphs with no K3,3K3,3-subdivisions in linear time. Labelled toroidal cores are enumerated, using matching polynomials of cycle graphs. As a result, we enumerate labelled graphs in TT having vertex degree at least two or three, according to their number of vertices and edges. We also show that the number m   of edges of graphs in TT satisfies the bound m⩽3n-6m⩽3n-6, for n⩾6n⩾6 vertices, n≠8n≠8.