The structure of image-subdivision-free toroidal graphs Original Research Article

We consider the class image of 2-connected non-planar image-subdivision-free graphs that are embeddable in the torus. We show that any graph in image 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 image-subdivisions in linear time. Labelled toroidal cores are enumerated, using matching polynomials of cycle graphs. As a result, we enumerate labelled graphs in image 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 image satisfies the bound image, for image vertices, image.