Is the Maximum Crossing Number Hereditary?



In a drawing of a graph in the plane some edges are allowed to cross, but only once at interior vertices and only if they are nonadjacent. The maximum crossing number of a graph G, cr_M(G), is the maximum number of pairwise edge crossings taken over all drawings of G.

Conjecture: If H is a subgraph of G, then cr_M(H) cannot exceed cr_M(G).

The obvious approach would be to take a drawing of H achieving the maximum crossing number and try to extend it to a drawing of G. The resulting drawing, if it existed, would provide the desired lower bound on the maximum crossing number of G. However, such an extension does not always exist. An example of this nonexistence is given in [RSP].

I believe that this conjecture is true.

References:

[RSP] R. Ringeisen, S. Steuckle, and B.L. Piazza, Subgraphs and bounds on maximum crossings, Bull. of the ICA 2 (1991) 33-46.


Submitted by : Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

August, 1995