Grid minors of graphs on the torus (Q1328384)

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. For example, the product of two \(n\)-cycles \(C_ n\times C_ n\) embeds on the torus with face-width \(n\); this embedding is called the toroidal \(n\)-grid. A graph \(H\) is a minor of \(G\) if we can create \(H\) from \(G\) by a sequence of edge deletions and edge contractions. The authors show that any graph embedded on the torus with face-width \(r\geq 5\) contains the toroidal \(\lfloor 2r/3 \rfloor\)-grid as a minor. Moreover, the value \(\lfloor 2r/3\rfloor\) is the best possible. An equivalent form of the result is that every toroidal graph with face- width at least \(\lceil 3k/2\rceil\) contains a toroidal \(k\)-grid as a minor. The proof proceeds by taking an embedded toroidal graph and constructing an associated planar polygon with integer coordinates which is symmetric about the origin. The grid minor corresponds to the existence of two linearly independent integer vectors of a certain length.