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