  We investigate the toroidal expanse of an embedded graph G, that is, the size
of the largest toroidal grid contained in G as a minor. In the course of this
work we introduce a new embedding density parameter, the stretch of an embedded
graph G, and use it to bound the toroidal expanse from above and from below
within a constant factor depending only on the genus and the maximum degree. We
also show that these parameters are tightly related to the planar crossing
number of G. As a consequence of our bounds, we derive an efficient constant
factor approximation algorithm for the toroidal expanse and for the crossing
number of a surface-embedded graph with bounded maximum degree.
