Return to Revisions

There should be a nice proof, but here is a reference that proves something stronger and weaker. This paper by de Graaf and Schrijver proves that every graph with face-width at least $n \geq 5$, contains the toroidal $\lfloor 2n/3 \rfloor$-grid as a minor. Note that the toroidal $\lfloor 2n/3 \rfloor$-grid has (almost) $8n^2/9$ edges. So any graph on the torus with face-width at least $n$ has (almost) $8n^2/9$ edges, which is pretty close to the conjectured answer of $n^2$.