Classification of minimal graphs of given face-width on the torus (Q1333341): Difference between revisions

The face-width of a graph embedded on the torus is the smallest \(n\) such that there is a noncontractible cycle on the torus which intersects the graph in exactly \(n\) points. This embedded graph is minimal if deleting or contracting any edge decreases the face-width. It is \(r\)-minimal if it is minimal with face-width \(r\). In this paper the author finds a correspondence between \(r\)-minimal toroidal graphs and certain polygons in the real plane. These polygons have integer coordinates and are symmetric about the origin. This correspondence gives a classification of the \(r\)-minimal graphs. Moreover, it allows the author to count, up to a natural equivalence, the number of \(r\)-minimal embedded graphs. This number is \(r^ 3/6+ 4r/3\) for \(r\) even and \(r^ 3/6+ 5r/6\) for \(r\) odd. The relationship between the face-width of a toroidal graph and the geometry of the plane integer lattice is beautiful. The reviewer strongly recommends reading this paper.