The maximum crossing number of $C_{3}\times C_{3}$

It was shown by Piazza et al [6] that the maximum crossing number of $C_{3}\times C_{3}$ lies somewhere between 68 and 80, inclusive. We resolve this by showing that the maximum crossing number is exactly 78. The proof uses a mixture of theoretical arguments as well as exhaustive computer searches. Although the proofs are ad hoc, we believe that the general techniques could be used to determine the maximum crossing number for other, similarly sized graphs.

We assume that the reader is familiar with the usual definitions from the theory of crossing numbers and graph drawings. For more detailed descriptions, we recommend [7]. A graph $G$ has the vertex set $V(G)$ and edge set $E(G)$. Let $C_{n}$ denote the cycle graph on $n$ vertices, and let $P_{m}$ denote the path graph on $m$ edges. Let $G\times H$ denote the graph Cartesian product between graphs $G$ and $H$. For example, $C_{3}\times C_{3}$ is displayed in Figure 1 $(a)$. A drawing, $D(G)$, provides a mapping of $E(G)$ and $V(G)$ into the plane. Vertices are mapped to distinct points and each edge $e=\{u,v\}$ is mapped to a conitnuous arc between the points associated with $u$ and $v$ in such a way that the interior of the arc does not contain any points associated with vertices. In addition, the interiors of the arcs are only allowed to intersect at singleton points, these are the crossings and the number of crossings of a drawing is denoted $cr_{D}(G)$. We shall refer to the points and arcs given by a drawing as the ‘vertices’ and ‘edges’ of the drawing. A drawing is a good drawing if an edge never crosses itself, incident edges do not cross each other and pairs of edges cross at most once. All drawings considered here are good and when we use the word ‘drawing’, we will mean ‘good drawing’. The maximum crossing number, denoted as $\operatorname{\text{maxcr}}(G)$, is the maximum number of edge crossings in any good drawing of $G$. As first described by Conway and Woodall [8], the thrackle number of $G$, denoted $Th(G)$, is the number

where $d(v)$ is the degree of vertex $v$. Obviously, for a given graph, the maximum crossing number may not be equal to the thrackle number, but if it is, then $G$ is thrackleable. Given a drawing $D$ of a graph $G$, if a pair of non-incident edges do not cross in $D$, then we say that they are a missed pair. Thus, for any good drawing $D$, $cr_{D}(G)$ is equal to the thrackle number minus the number of missed pairs. Note that the graph $C_{4}$ is not thrackleable, and similarly, it was shown in [4] that the bowtie graph, displayed in Figure 1 $(b)$, is also not thrackleable. Thus, any drawing of $C_{4}$ or a bowtie has at least one missed pair. The sub-thrackle number, denoted $STh(G)$, is $Th(G)$ minus the number of subgraphs of $G$ that are isomorphic to $C_{4}$ plus the number subgraphs isomorphic to the complete graph on 4 vertices. It follows that, for any graph $G$, $\operatorname{\text{maxcr}}(G)\leq STh(G)$. For a graph $G$, we define a prescription, denoted $P$, to be a mapping $P:E(G)\rightarrow 2^{E(G)}$, where $2^{E(G)}$ is the power set of $E(G)$. For each edge $e$, $P(e)$ gives an unordered set of edges, which we call the virtual crossings of $e$. If a drawing $D$ of $G$ is such that each edge $e$ crosses exactly those edges in $P(e)$, then $D$ satisfies the prescription $P$. Clearly, any drawing of $G$ satisfies some prescription $P$, however, it may be the case that there is no drawing that satisfies a given $P$. We shall be concerned with identifying when it is impossible to satisfy $P$.

After discussing some technical lemmas in Section 3, we shall show the following in Section 4

Given a drawing of a graph, let $m(A,B)$ be the number, modulo 2, of missed pairs with one of the edges belonging to the edge set $A$ and the other edge belonging to edge set $B$. A property that has been used several times before, e.g. see [8], is as follows

For a prescription $P$ of $G$, we shall say that $P$ satisfies property 1 if, for the edges of any two vertex disjoint cycles of $G$, the virtual crossings given by $P$ do not contradict the condition in Lemma 3.1.

The graph displayed in Figure 2 $(a)$ is $C_{3}\times P_{1}$ (sometimes called the envelope graph) and $C_{3}\times C_{3}$ contains 9 subgraphs isomorphic to this graph. We have the following

Proof.   Figure 2 $(b)$ displays $C_{3}\times P_{1}$ drawn with 15 crossings which provides a lower bound and $STh(C_{3}\times P_{1})=15$ which provides the matching upper bound. \qed

Next, $C_{3}\times P_{1}$ is small enough to use an exhaustive computer search to confirm that there are no drawings of $C_{3}\times P_{1}$ with exactly 14 crossings. Hence, every drawing of $C_{3}\times P_{1}$ has either 15 crossings or fewer than 14 crossings. We note that for larger graphs, exaustive searches such as this quickly become intractable.

For a prescription $P$ of $G$, we shall say that $P$ satisfies property 2 if, for any subgraph of $G$ which is isomorphic to $C_{3}\times P_{1}$, the virtual crossings given by $P$, restricted to the subgraph, provide a total of either 15 or fewer than 14 virtual crossings.

Next, consider a graph consisting of a cycle of length 6, and one additional edge which forms a triangle. In the notation of [3], this is a $DB(5,3,-1)$ graph. In [5], Harborth found all thrackleable graphs on six vertices, which does not include $DB(5,3,-1)$ and so there must exist at least one missed pair in any drawing of $DB(5,3,-1)$. Hence, along with the drawing of $DB(5,3,-1)$ in Figure 2 $(c)$, which has 10 crossings, we conclude that $\operatorname{\text{maxcr}}(DB(5,3,-1))=Th(DB(5,3,-1))-1=10$.

For a prescription $P$ of $G$, we shall say that $P$ satisfies property 3 if, for any subgraph of $G$ which is isomorphic to $DB(5,3,-1)$, the virtual crossings given by $P$, restricted to the subgraph, provide at most 10 virtual crossings.