Classification of Minimal Graphs of Given Face-Width on the Torus

For any graph G embedded on the torus, the face-widthr(G) of G is the minimum number of intersections of G and C, where C ranges over all nonnullhomotopic closed curves on the torus. We call Gr-minimal if r(G) ≥ r and r(G′) < r for each proper minor G′ of G. We classify the r-minimal graphs by means of certain symmetric integer polygons in the plane R2. Up to a certain natural equivalence, the number of r-minimal graphs on the torus is equal to 16r3 + 56r if r is odd and to 16r3 + 43r if r is even.