GRAPHS ON THE TORUS AND GEOMETRY OF NUMBERS

We show that if G is a graph embedded on the torus S and eaeh nonnullhomotopic closed curve on S intersects G at least r times, then G contains at least ⌊ 3 4r⌋ pairwise disjoint nonnulihomotopic circuits. The factor 3 4 is best possible. We prove this by showing the equivalence of this bound to a bound in the two-dimensional geometry of numbers. To show the equivalence, we study integer norms, i.e., norms || · || such that ||x|| is an integer for each integer vector x. In particular, we show that each integer norm in two dimensions has associated with it a graph embedded on the torus, and conversely. © 1993 Academic Press, Inc.