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