Trading crossings for handles and crosscaps

Abstract

Let $c_k = cr_k(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} $c_0,c_1,c_2,dots$ encodes the trade-off between adding handles and decreasing crossings. We focus on sequences of the type $c_0 > c_1 > c_2 = 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 $c_1/c_0 > 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} $tilde c_0, tilde c_1, tilde c_2,dots$ for drawings on non-orientable surfaces. We show that for every $tilde c_0 > tilde c_1 > 0$ there exists a graph with non-orientable crossing sequence $tilde c_0, tilde c_1, 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).