Trading crossings for handles and crosscaps

Abstract

Let ck=crk(G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) {em crossing sequence} c0,c1,c2,dots encodes the trade-off between adding handles and decreasing crossings. We focus on sequences of the type c0>c1>c2=0; equivalently, we study the planar and toroidal crossing number of doubly-toroidal graphs. For every epsilon>0 we construct graphs whose orientable crossing sequence satisfies c1/c0>5/6−epsilon. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save 5 times more crossings. We similarly define the {em non-orientable crossing sequence} tildec0,tildec1,tildec2,dots for drawings on non-orientable surfaces. We show that for every tildec0>tildec1>0 there exists a graph with non-orientable crossing sequence tildec0,tildec1,0. We conjecture that every strictly-decreasing sequence of non-negative integers can be both an orientable crossing sequence and a non-orientable crossing sequence (with different graphs).