A Crossing Number Hereditary under Minors

In a *drawing* of a graph *G* in the plane two edges may cross, but only transversally at interior points and only if they are nonadjacent. The *crossing number* *cr(G)* is the minimal number of pairwise edge crossings over all drawings of *G* in the plane.

The following problem arises out of a lament from Paul Seymour: ``Isn't it a shame that crossing numbers don't work well with minors?'' The difficulty is that an edge contraction *G/e* can have strictly larger crossing number than *G*. The reason is that if edges *e* and *f* cross in a drawing of *G*, then *f* passes through the vertex *e* in the corresponding drawing of *G/e*. It is not too hard to find such examples using a plane drawing with every face a triangle except for one quadrilateral containing two pairwise crossing diagonals *e* and *f*.

**Problem:** *Give a careful definition of* cr^*, *a variation of the crossing number, so that* cr^*(H) *cannot exceed* cr^*(G) *for every minor* H *of* G.

There are some subtleties involved; for example, edges may touch nontransversally when passing through vertices. It is helpful that edge deletion cannot increase the crossing number. This problem may not be too difficult; I have not given it much thought.

Assuming the first problem is solved, let *P_k* be the class of graphs *G* satisifying cr^*(G) does not exceed *k*. Then *P_k* is hereditary, that is, if *G* is in *P_k* and *H* is a minor of *G*, then *H* is in *P_k*. It follows from the work of Robertson and Seymour on Wagner's Conjecture that for each *k* there is a finite set of graphs *H_1,..., H_n* such that *G* has crossing number at most *k* if and only if it contains no *H_i* as a minor.

**Problem:** *Find these forbidden minors for small values of* k *(as large a value of* k *as seems feasible)*.

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA. (With thanks to Paul Seymour)

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

August, 1995