Trading crossings for handles and crosscaps

Dan Archdeacon, C. Paul Bonnington and Jozef Siran

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).


Keywords
Embedding graphs, crossing number

Math Review Classification
Primary 05C10

Last Updated
29 November 2000

Length
12

Availability
This article is available in: