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