Trading Handles for Crossings

Let *S_g* denote the orientable surface of genus *g*, that is, the sphere with *g* handles attached. A *drawing* of a graph *G* on surface *S_g* allows edges to cross pairwise if they are nonadjacent. It is desired to find the minimum number of crossings over all such drawings. Denote this minimum by *cr(G,S_g)*.

Clearly *cr(G,S_g)* is at most *(G,S_{g+1}) - *1. That is, by adding a handle one can save on the number of crossings. In fact, it is easy to construct examples where the gap *cr(G,S_{g+1}) - cr(G,S_g)* is arbitrarily large. To wit, consider a large plane triangulation *T* with two vertices *u* and *v* far apart. Adding in the edge *uv* makes a toroidal graph with large planar crossing number.

We are interested in the sequence *cr_n (G) = cr (G,S_n)*. Call *cr_0(G), cr_1(G), cr_2(G), ...* the *crossing sequence* of *G*.

**Question:** *Which sequences are crossing sequences?*

As noted above, these sequences must be strictly decreasing (until they reach zero) and can have arbitrarily large gaps.

With a variation on the above construction Archdeacon, Bonnington, and Siran [ABS] can construct graphs achieving any sequence satisfying *c_{n+1} - c_n* at most *c_n - c_{n-1}* (that is, any sequence where the gaps do not increase). One might expect that that is the desired characterization. After all, if adding in a second handle produces greater savings than adding in the first handle, then why didn't you add the second handle first?

Confounding this intuitively appealing argument, we have constructions where *(c_{n+1} - c_n) / (c_n - c_{n-1}) *is arbitrarily close to 6. Adding a handle can save more crossings than the previous handle, but not by an arbitrarily large ratio. I boldly conjecture (with some reservations from my co-authors) that:

**Conjecture:** *Every sequence is a crossing sequence.*

There is an obvious analogue about the crossing sequence for graphs embedded on non-orientable surfaces. To this end we [ABS] have shown that any sequence *c_0 > c_1 > c_2 = 0* is the non-orientable crossing sequence of some graph. This supports my bold conjecture.

Jozef Siran introduced me to the problem. To my knowledge we are the only people who have worked on it.

References:

[ABS] D. Archdeacon, P. Bonnington, J. Siran, How to eliminate crossings by adding handles or crosscaps, preprint.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT, 05405 USA.

Send comments to *dan.archdeacon@uvm.edu*

August, 1995. Modified November, 1998