Electronic Journal of Graph Theory and Applications

Michal Staš, Juraj Valiska

Department of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and Informatics, Technical University, 042 00 Košice, Slovak Republic

michal.stas@tuke.sk, juraj.valiska@tuke.sk

The crossing number \(\operatorname{cr}(G)\) of a graph G is the minimum number of edge crossings over all drawings of G in the plane, and the optimal drawing of G is any drawing at which the desired minimum number of crossings is achieved. We conjecture that a complete graph \(K_n\) is \(\mathcal{CF}\)-connected if and only if it does not contain a subgraph of \(K_8\), where a connected graph G is \(\mathcal{CF}\)-connected if there is a path between every pair of vertices with no crossing on its edges for each optimal drawing of G. We establish the validity of this Conjecture for the complete graphs \(K_n\) for any \(n \leq 12\), and by assuming the Harary-Hill's Conjecture that \(\operatorname{cr}(K_n) = H(n) = \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor\) is also valid for all n > 12. The proofs of this paper are based on the idea of a new concept of a crossing sequence.

Keywords: crossing number, optimal drawing, crossing sequence, connectivity, complete graph

Mathematics Subject Classification: 05C10, 05C38

DOI: 10.5614/ejgta.2023.11.2.12

1. Introduction

Our initial intention was whether it is possible to describe a family of graphs for which it is possible to find the optimal drawing so that after removing the crossed edges we get a disconnected subgraph. It is obvious that for this reason we will only deal with the finite connected graphs. In the search for the mentioned family of graphs, the importance of various structural properties of the complete graph \(K_8\) gradually became apparent, that is, \(K_8\) is the first of all complete graphs for which it is possible to achieve a disconnected subgraph induced on the uncrossed edges of some

Received: 3 November 2020, Revised: 26 September 2023, Accepted: 28 September 2023.

its optimal drawing. This fact allow us to establish a new Conjecture that a complete graph \(K_n\) is \(\mathcal{CF}\)-connected if and only if it does not contain a subgraph of \(K_8\). It is well known that the problem of reducing the number of crossings on the edges in the drawings of graphs was studied in many areas, and the most prominent area is VLSI technology. So, this new property \(\mathcal{CF}\)-connectedness of graphs is studied only for the drawings of graphs with the smallest number of crossings, that is, on their optimal drawings. The main aim of the paper is to establish an unambiguous characterization of \(\mathcal{CF}\)-connected graphs in a manner similar to that of the well-known Kuratowski's theorem giving a necessary and sufficient condition for planarity of graphs.

We already know several hypotheses in the cross-graph theory. One of the oldest crossing number open problem is Guy's Conjecture [3] or Harary-Hill's Conjecture [4] about the number of crossings of the complete graphs \(K_n\) saying that the upper bound \(\operatorname{cr}(K_n) \leq \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor\) holds with equality. Recently, this Conjecture was proved for n at most 12 by Pan and Richter [6], and it is "asymptotically at least 98,5% true" by Balogh \(et\ al.\) [2]. The validity of this hypothesis confirms the correctness of our hypothesis. In the future, it would certainly be worth mentioning to show or refute whether these two hypotheses happen to be equivalent in some way. In Section 3, Theorems 3.1 and 3.2 also offer quite surprising conclusions about the behavior of optimal drawings of the complete graphs \(K_n\). The idea of a new concept of a crossing sequence will be strongly used in their proofs. These results could be used in some way in a confirming the mentioned Harary-Hill's Conjecture. The issue regarding \(\mathcal{CF}\)-connectedness for complete bipartite graphs \(K_{m,n}\) has already been resolved by Staš and Valiska [8].

2. Definitions and Preliminary Results

The crossing number \(\operatorname{cr}(G)\) of a simple graph G with the vertex set V(G) and the edge set E(G) is the minimum possible number of edge crossings in a drawing of G in the plane. (For the definition of a drawing see [5].) It is easy to see that a drawing with minimum number of crossings (an optimal drawing) is always a good drawing, meaning that no edge crosses itself, no two edges cross more than once, and no two edges incident with the same vertex cross.

Let D be an optimal drawing of the graph G=(V,E) with \(V(G)=\{v_1,v_2,\ldots,v_n\}\). Let \(\operatorname{cr}_D(v_i), 1 \leq i \leq n\), denote the number of crossing on the edges which are incident with the fixed vertex \(v_i\). Since every optimal drawing is a good drawing, each crossing in D is counted on two edges with four vertices at their ends. This means that

\[\sum_{i=1}^{n} \operatorname{cr}_{D}(v_{i}) = 4 \operatorname{cr}_{D}(G), \tag{1}\]

where \(\operatorname{cr}_D(G)\) denotes the number of crossings in D. The crossing sequence \(d_{D(G)}\) of the graph G in the drawing D is the non-increasing sequence of its vertex crossings \(\operatorname{cr}_D(v_i)\). The crossing sequence is a drawing of graph invariant so two isomorphic drawings of one graph have the same crossing sequence. However, the crossing sequence does not, in general, uniquely identify a drawing of graph; in some cases, non-isomorphic drawings of the same graph have the same crossing sequence. For example, it is not such a big problem to find a few non-isomorphic optimal drawings of the complete graph \(K_8\). In the proof of Theorem 3.2, it will be mentioned that just one crossing sequence can be obtained for all optimal drawings of the graph \(K_8\).

Figure 1. Planar drawings of the complete graphs K1, K2, K3, and K4.

For any optimal drawing D of G = (V, E), let us denote by CFD(G) the subgraph of G with the vertex set V (G) and the edge set {e ∈ E(G) : crD(G) = crD(G \ e)}. A connected graph G is said to be CF-connected if its subgraph CFD(G) is connected for each optimal drawing D of G. Equivalently, we can also say that a connected graph G is CF-connected if there is a path between every pair of vertices with no crossing on its edges for each optimal drawing D of G. Since there are planar drawings of the complete graphs Kⁱ , i = 1, 2, 3, 4, as shown in Figure 1, the graphs K1, K2, K3, and K⁴ are CF-connected.

3. The complete graphs Kn, for 5 ≤ n ≤ 8

Theorem 3.1. If D is any optimal drawing of the complete graph Kn, for 2 ≤ n ≤ 8, then there is at least one vertex v of Kⁿ such that the subdrawing of the subgraph Kⁿ \ v obtained by removing the vertex v from Kⁿ induced by D is also optimal drawing of Kn−1.

Proof of Theorem 3.1. As cr(Kn) = 0 for any n = 1, 2, 3, 4, the result is obviously valid for each n = 2, 3, 4. Suppose now that, for n = 8, there is an optimal drawing D of the graph K⁸ with no possibility to remove one vertex v from K⁸ for an obtaining optimal drawing of the graph K⁷ induced by D. The uniqueness of the crossing sequence dD(K8) enforces that all its members have values of at most eight provided by cr(K8) − cr(K7) − 1 = 18 − 9 − 1 = 8. If dD(K8) = (8, 8, 8, 8, 8, 8, 8, 8), then crD(K8) = 16 < 18 = cr(K8) by (1) in the form 64 = 4 crD(K8). Clearly, the same contradiction with the optimality of the drawing D of K⁸ is also obtained if crD(vi) < 8 in the sequence dD(K8) for some i ∈ {1, . . . , 8}. The proof proceeds in the similar way also for n = 5, 6, 7. ✷

Theorem 3.1 does not apply to n = 9 and n = 11 because of the optimal drawings of the graphs K⁹ and K¹¹ in Figure 2, and by cr(K9) − cr(K8) = 18 and cr(K11) − cr(K10) = 40. Currently, the crossing numbers cr(Kn) for n at most 12 are known. If we used the same idea as in the proof of Theorem 3.1, we could extend this result for n = 10 and n = 12. However, the natural question remains still open whether Theorem 3.1 can be generalized for the remaining even natural numbers n greater than 8.

Figure 2. Optimal drawing D of K⁹ with dD(K9) = (16, 16, 16, 16, 16, 16, 16, 16, 16) and optimal drawing D of K¹¹ with dD(K11) = (39, 39, 39, 39, 39, 35, 35, 35, 35, 35, 30).

Corollary 3.1. There is only one optimal drawing of K⁵ and of K6.

Proof. By Theorem 3.1, all optimal drawings of K⁵ can be obtained from the planar drawing of K⁴ in Figure 1 by adding one vertex with four corresponding edges. Because all regions of this planar drawing of K⁴ are same related to the graph K4, there is only one optimal drawing of K⁵ as shown in Figure 3. Similarly, every optimal drawing of K⁶ can only be achieved by adding a new vertex with five corresponding edges in the region of the optimal drawing of K⁵ with three vertices of the graph K⁵ on its boundary. From the point of view of adding a new vertex with just two new crossings, all four triangular regions are identical, which yields that there is also only one optimal drawing of K⁶ presented in Figure 3. ✷

Figure 3. Optimal drawings of the complete graphs K⁵ and K6.

For easier and more accurate labeling in the proof of the following Corollary 3.2, let us define notation of regions in the optimal drawing of the graph \(K_6\) as shown in Figure 4 with the corresponding vertex notation and also with the numbering of three forced crossings. This unique drawing of \(K_6\) (with respect to possible isomorphisms) contains fourteen different regions. Let us denote these regions by \(\omega_{1,2,3}\), \(\omega_{4,5,6}\), \(\omega_{1,2}^1\), \(\omega_{2,6}^1\), \(\omega_{1,5}^1\), \(\omega_{1,5}^2\), \(\omega_{1,3}^2\), \(\omega_{1,5}^2\), \(\omega_{3,4}^2\), \(\omega_{2,3}^3\), \(\omega_{2,6}^3\), \(\omega_{3,4}^3\), and \(\omega_{4,6}^3\) depending on which of vertices or crossings are located on the boundary of the corresponding region.

Figure 4. Optimal drawing of \(K_6\) with the vertex notation and the numbering of three forced crossings.

Corollary 3.2. There are five non-isomorphic optimal drawings of \(K_7\).

Proof. We will discuss the existence of all possible crossing sequences in an effort to find a description of all non-isomorphic optimal drawings of the complete graph \(K_7\). Let us suppose some optimal drawing D of \(K_7\), which yields that \(\sum_{i=1}^7 \operatorname{cr}_D(v_i) = 36\) by (1) using \(\operatorname{cr}_D(K_7) = 9\). All members of the crossing sequence \(d_{D(K_7)}\) are at most six provided by \(\operatorname{cr}(K_7) - \operatorname{cr}(K_6) = 9 - 3 = 6\), and this value of six is also included therein at least once due to Theorem 3.1. Further, also by Theorem 3.1, let D' be the optimal drawing of the subgraph \(K_6\) obtained by removing the vertex \(v_7\) from \(K_7\) induced by D. In the rest of the proof, based on their symmetry, let us assume this drawing D' with the vertex notation of \(K_6\) as shown in Figure 4, and let also \(\operatorname{cr}_D(v_1)\) be one of the smallest values in the sequence \(d_{D(K_7)}\).

Now, let us turn to the possibilities of a placing the vertex \(v_7\) in any of the fourteen regions of the drawing D' of \(K_6\). If \(v_7 \in \omega_{2,3}^3\), then the edges \(v_2v_3\), \(v_3v_6\), and \(v_2v_4\) must be crossed by the edges \(v_7v_1\), \(v_7v_4\), and \(v_7v_6\), respectively, and there is no crossing on the edges \(v_7v_2\) and \(v_7v_3\) in D. This enforces that the edge \(v_7v_5\) of the graph \(K_7\) contributes just three crossings to achieve the optimal drawing D with \(\operatorname{cr}_D(K_7) = 9\). Moreover, the edges \(v_1v_2\) and \(v_1v_6\) cannot be crossed by \(v_7v_5\) at the same time, otherwise, we get a contradiction with the supposed minimum of \(\operatorname{cr}_D(v_1) = 5\) according to \(\operatorname{cr}_D(v_4) = 4\). From the symmetry of D', \(\operatorname{cr}_D(v_6) = 4\) contradicts the supposed minimum of \(\operatorname{cr}_D(v_1) = 5\) if the edges \(v_1v_3\) and \(v_1v_4\) are crossed by \(v_7v_5\). If the edge \(v_7v_5\) crosses the edges \(v_2v_4\), \(v_2v_6\), and \(v_1v_6\), then we obtain one of the desired optimal drawings of \(K_7\) denoted as type \(A_1\) and its isomorphic drawing is given in Figure 5. This type \(A_1\) is represented by \(d_{D(K_7)} = (6,6,6,5,5,4,4)\) and by exactly nine edges that are not crossed in D. It is not

difficult to verify that we could obtain an isomorphic optimal drawing of \(K_7\) with the previous case if the edge \(v_7v_5\) crosses the edges \(v_3v_6\), \(v_3v_4\), and \(v_1v_4\). The type \(\mathcal{A}_4\) in Figure 5 represented by \(d_{D(K_7)}=(6,6,6,5,5,5,3)\) can be obtained if the edge \(v_7v_5\) crosses the edges \(v_2v_4\), \(v_3v_6\), and \(v_4v_6\). Based on the symmetry of \(D^{'}\), it is not necessary to analyze all remaining regions in this way. By applying the similar arguments as in the first region, we receive both types \(\mathcal{A}_2\) and \(\mathcal{A}_5\) if \(v_7\in\omega_{1,2,3}\cup\omega_{4,5,6}\). Types \(\mathcal{A}_1\) and \(\mathcal{A}_3\) are achieved if \(v_7\in\omega_{2,6}^3\). Types \(\mathcal{A}_1\) \(\mathcal{A}_2\), and \(\mathcal{A}_3\), if the vertex \(v_7\) is placed in the regions \(\omega_{1,2}^1\), \(\omega_{2,6}^1\), and \(\omega_{5,6}^1\), respectively. Let us note that the type \(\mathcal{A}_2\) is represented by \(d_{D(K_7)}=(6,6,6,5,5,4,4)\) and by exactly ten edges that are not crossed in D. \(\square\)

Figure 5. Five non-isomorphic optimal drawings of the complete graph \(K_7\).

For all optimal drawings of the graphs \(K_i\), i = 5, 6, 7, presented in Figure 3 and Figure 5, it is not difficult to verify that their corresponding subgraph \(CF_{D(K_i)}\) is connected. So, the complete graphs \(K_5\), \(K_6\), and \(K_7\) are also \(\mathcal{CF}\)-connected.

Theorem 3.2. Let D be any optimal drawing of the complete graph \(K_8\). The subdrawing of the subgraph \(K_8 \setminus v\) obtained by removing any vertex v from \(K_8\) induced by D is also optimal drawing of \(K_7\).

Proof of Theorem 3.2. Let D be any optimal drawing of the graph \(K_8\), that is, \(\operatorname{cr}_D(K_8)=18\). As \(\operatorname{cr}(K_7)=9\), the crossing sequence \(d_{D(K_8)}\) consists of values at most nine, otherwise, by deleting the vertex \(v_i\) of \(K_8\) with \(\operatorname{cr}_D(v_i)>9\), a drawing of the graph homeomorphic to \(K_7\) with fewer than nine crossings is obtained. Further, by (1) in the form \(\sum_{i=1}^8\operatorname{cr}_D(v_i)=72\), none of the values in the sequence \(d_{D(K_8)}\) can be fewer than nine. So, \(d_{D(K_8)}=(9,9,9,9,9,9,9,9)\) and this also enforces that there are exactly nine crossings on the edges incident with any vertex \(v_i\) of the graph \(K_8\) in the considered drawing D.

The same idea of an identical crossing sequence as in the proof of Theorem 3.2 can be also applied for the complete graphs \(K_{10}\) and \(K_{12}\). Of course, assuming the validity of the Harary-Hill's Conjecture, the same results hold for the remaining even natural numbers n greater than 12, and all members of the crossing subsequence \(d_{D(K_n)}\) are going equal to \(\frac{(m-1)^2(m-2)}{2}\), where n=2m. However, it is not difficult to verify in possible regions of all drawings in Figure 5 that only for the optimal drawing of \(K_7\) of type \(\mathcal{A}_1\), there is a possibility to achieve an optimal drawing D of the graph \(K_8\) by adding one new vertex requesting a disconnected subgraph \(CF_{D(K_8)}\). This contemplated drawing D of \(K_8\) can be isomorphically redrawn as shown in Figure 6(a). Thus, the next result is obvious.

Corollary 3.3. The complete graph \(K_8\) is not \(C\mathcal{F}\)-connected.

4. The Harary-Hill's Conjecture

Guy [3] estimated the upper bound \(\frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor\) which is conjectured to be equal to the crossing number of the complete graph \(K_n\). The same conjecture was also proposed by Harary and Hill [4] at around the same time, that is, the minimum number of crossings among all drawings of the complete graph \(K_n\) is equal to the Hill's number \(H(n) = \frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor\). Several exact values for the crossing number of the graphs \(K_n\) are based on the following theorem presented in [3].

Theorem 4.1. If the Guy's Conjecture holds for the graphs \(K_{n-1}\), such that n is even, then it holds also for the graphs \(K_n\).

For n even, the idea of the crossing sequence \(d_{D(K_n)}\) in the proof of Theorem 3.2 can also be used to determine the proof of Theorem 4.1 provided that

\[\frac{1}{4}\frac{n-2}{2}\frac{n-2}{2}\frac{n-4}{2}\frac{n-4}{2} + \frac{\left(\frac{n}{2}-1\right)^2\left(\frac{n}{2}-2\right)}{2} = \frac{1}{4}\frac{n}{2}\frac{n-2}{2}\frac{n-2}{2}\frac{n-4}{2}.\]

Pan and Richter [6] confirmed the validity of this Conjecture for the graph \(K_{11}\), which yields that also for the graph \(K_{12}\) by Theorem 4.1. Consequently, Balogh et al. [2] obtained the best known asymptotic lower bound for the crossing number of \(K_n\) in the form

\[\lim_{n \to \infty} \frac{\operatorname{cr}(K_n)}{\frac{1}{4} \lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}{2} \rfloor \lfloor \frac{n-2}{2} \rfloor \lfloor \frac{n-3}{2} \rfloor} > 0.985,\]

which implies that it is "asymptotically at least 98,5% true". So, for \(n \ge 13\), the following claims will be so far verified under the assumption of the Guy's Conjecture.

Figure 6. Harary-Hill drawings of K⁸ and of K10.

Figure 7. Harary-Hill drawing of K12.

Based on the idea of constructing a Hill drawing Hⁿ of Kn, Abrego ´ et al. [1] have been described the cylindrical drawing H2^m of K2^m with exactly H(2m) crossings, for m ≥ 3. In this good drawing H2m, all vertices are contained in two regular convex polygons U = {u1, u2, . . . , um} and V = {v1, v2, . . . , vm} (labeled clockwise), and both are centered around the middle of w. Polygon U is greater than V , and they are positioned in such a way that u1, w, and v¹ are collinear if m is odd, and u1, w, and the midpoint of v1v^m are collinear if m is even, see Figure 6 and 7.

The edges joining two vertices of V are placed inside (or on the boundary of) V , the edges joining two vertices of U are placed outside (or on the boundary of) U, and the edges joining vertices of U with vertices of V are outside V and inside U in such a way, that for every 1 ≤ i ≤ m edge uiv^j goes along the polygon V in counterclockwise direction for j ∈ {i, i + 1, i + 2, . . . , i + ⌈ m−1 2 ⌉}, values taken modulo m, and in clockwise direction otherwise. However, the number of crossings in the drawing H2^m presented in [1] is not proved in any way, and so the following statement is necessary for our research.

Theorem 4.2. The cylindrical drawing H2^m of the complete graph K2^m enforces exactly H(2m) crossings, for m ≥ 3.

Proof of Theorem 4.2. Richter and Thomassen [7] estimated the number of crossings in a cylindrical drawing of Km,m by the lover bound m m 3 . Since each crossing inside the polygon V is uniquely identified by two edges with four vertices at their ends, the number of crossings inside the polygon ^V is equal to m 4 . The same holds for the outside the polygon U, and therefore, the number of crossings of K2^m in the drawing H2^m is given by

\[m\binom{m}{3} + 2\binom{m}{4} = \frac{m(m-1)^2(m-2)}{4} = \frac{1}{4} \left\lfloor \frac{2m}{2} \right\rfloor \left\lfloor \frac{2m-1}{2} \right\rfloor \left\lfloor \frac{2m-2}{2} \right\rfloor \left\lfloor \frac{2m-3}{2} \right\rfloor = H(2m).\]

Because in such a drawing of K2^m only the edges of u1, u2, . . . , um, u¹ and v1, v2, . . . , vm, v¹ are not crossed, we get the following result.

Corollary 4.1. The complete graphs K¹⁰ and K¹² are not CF-connected. If cr(Kn) = H(n), then Kⁿ is not CF-connected, for any n > 12 even.

For n ≥ 9 odd, it is possible to use the construction a drawing Nm,m,¹ of the complete graph K2m+1 with H(2m + 1) crossings. Its description together with the proof of the number of crossings can be found in Abrego ´ et al. [1]. We have already presented the drawing N5,5,¹ of K¹¹ in Figure 2(b). As in such a drawing of K2m+1 all edges are crossed at least once, the next result is obvious.

Corollary 4.2. The complete graphs K⁹ and K¹¹ are not CF-connected. If cr(Kn) = H(n), then Kⁿ is not CF-connected, for any n > 12 odd.

5. Conclusions

We suppose that the application of the crossing sequences of considered optimal drawings can be used to estimate another families of \(\mathcal{CF}\)-connected graphs, mainly for the graphs with the already well-known crossing numbers. Theorems 3.1 and 3.2 offer partial answers to remove some vertex from any optimal drawing of the complete graph \(K_n\) in order to obtain an optimal drawing of \(K_{n-1}\). Moreover, assuming the validity of Harary-Hill's Conjecture, Theorem 3.1 does not apply to any n odd at least 13 using the aforementioned drawing \(N_{m,m,1}\). The same idea as in the proof of Theorem 3.2 can also be used to n=10,12, and for n even greater than 12 provided that \(\operatorname{cr}(K_n)=H(n)\). In this case, all members of the crossing sequence of each optimal drawing of \(K_n\) are going equal to \(\frac{(m-1)^2(m-2)}{2}\), where n=2m.

Acknowledgment

The research was supported by the internal faculty research project no. FEI-2020-69.

References

• [1] B.M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, and B. Vogtenhuber, Non-shellable drawings of \(K_n\) with few crossings, CCCG 2014 Halifax, Nova Scotia, August 11–13 (2014).
• [2] J. Balogh, B. Lidický, and G. Salazar, Closing in on Hill's Conjecture, SIAM J. Discrete Math. 33(3) (2019), 1261–1276.
• [3] R.K. Guy, A combinatorial problem, Nabla (Bull. Malayan Math. Soc.) 7 (1960), 68–72.
• [4] F. Harary and A. Hill, On the number of crossings in a complete graph, Proc. Edinburgh Math. Soc. 13 (1963), 333–338.
• [5] M. Klešč, The crossing numbers of join of the special graph on six vertices with path and cycle, Discrete Math. 310(9) (2010), 1475–1481.
• [6] S. Pan and R. B. Richter, The crossing number of \(K_{11}\) is 100, J. Graph Theory 56(2) (2007), 128–134.
• [7] R.B. Richter and C. Thomassen, Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs, The American Mathematical Monthly 104(2) (1997), 131–137.
• [8] M. Staš and J. Valiska, On problems of \(\mathcal{CF}\)-connected graphs for \(K_{m,n}\). Bull. Aust. Math. Soc. 104(2) (2021), 203-210.