Two Graphs on the Torus
Dan Archdeacon
University of Vermont

Consider a red graph and a green graph drawn on a torus. Two edges of the same color are not allowed to cross; however, a red edge can cross a green edge. The problem is to shift the two graphs on the torus so as to minimize the number of red/green edge-crossings. In this talk we give some upper and lower bounds on this minimum number; in many cases giving exact answers. We also discuss what happens if one drawing can be replaced with its mirror image: savings can result, but not too much.