# Calculating Crossing Numbers of Graphs Using Combinatorial Principles

Authors: Zhenhua Su
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The crossing numbers of graphs were started from Turán’s brick factory problem (TBFP). Because of its wide range of applications, it has been used in computer networks, electrical circuits, and biological engineering. Recently, many experts began to pay much attention to the crossing number ofG\e, which obtained from graph G by deleting an edge e. In this paper, by using some combinatorial skills, we determine the exact value of crossing numbers of K1,4,n\e and K2,3,n\e. These results are an in-depth work of TBFP, which will be beneficial to the further study of crossing numbers and its applications.


---

## Body

## 1. Introduction

The concept of crossing number was introduced by the Hungarian mathematician Turán [1]. He encountered a practical problem in Budapest brick factory, which named “Turán’s brick factory problem”(TBFP). In fact, TBFP is to determine the minimal number of crossings among edges of the complete bipartite graph Km,n.In the past five decades, it turned out that the crossing numbers have strong practical significance. And they can be widely used in various fields, such as the VLSI circuit layout [2], the identification and repaint of sketch [3], and automatic generation of ER diagram in software development [4] (see [5, 6]). One of important applications is to find the best location for a new electrical substation so that every two substations are directly connected and to do without overlapping power lines. Rach [7] has applied the crossing number to solve a problem of locating electrical substations in the city of Glencoe, MN.With the depth of research, the crossing numbers of graphs have been investigated extensively in the mathematical, computer, and biological literature, often under different parameters, such as the parity [8], odd-crossing number [9], regular graphs [10], chromatic number [11], and genus [12]. For more results and its properties about crossing numbers, reader can refer to [13–16]. As for the complete bipartite graphs Km,n, Kleitman in [17] proved that(1)crKm,n=m2m−12n2n−12=Zm,n,m≤6,m≤n.Recently, the crossing numbers of complete multipartite graphs attracted much attention. In 1986, Asano [18] obtained the crossing numbers of graphs K1,3,n and K2,3,n. In 2008, Huang and Zhao in paper [19] established that the crossing number of graph K1,4,n is equal to nn−1. In 2020, the crossing numbers of graphs K1,1,4,n as well as K1,1,4□T have been proved in [20].While studying the crossing number of the primal graphG, many experts also began to follow with interest the crossing number of G\e, which is obtained by deleting an edge e from G. This is an interesting problem worthy of consideration. For G, it is a complete graph or complete bipartite graph. Ouyang in [21, 22] as well as Chia in [23], independently, established the precise values of crossing numbers of certain graphs G\e: (1) Kn\e for n≤12, (2) Km,n\e for m=3,4 and n≥1.Very recently, Huang and Wang in [24] by applying the method of edge-labeling, which is new and different from those used in [22, 23], have proved that crKm,n\e=n−1n−2. In the present paper, We attempt to study the crossing number of graph G\e, where G is a complete tripartite graph. Using Huang’s result and some combinatorial skills, we establish exact value of crossing numbers of K1,4,n\e and K2,3,n\e.Terms and definitions involved in the paper follow as those in [24]. Given a simple graph G, the crossing number denoted by crG is the minimum number of crossings in any good drawing of graph G. The good drawing with minimum number of crossings is called the optimal drawing. For a vertex v∈VG, Ev is used to represent all edges which is incident with v. The responsibilities of v, denoted rDv, are defined to be the sum of crossings of all edges incident to v in the drawing D.


## 2. Crossing Number ofK1,4,n\e

LetX,Y,Z be the vertex partition of the graph K1,4,n, where X=x, Y=y1,y2,y3,y4, and Z=z1,z2,…,zn. Let XY, XZ, and YZ be the subgraphs of K1,4,n induced by X∪Y, X∪Z, and Y∪Z, respectively. Clearly, XY≅K1,4. For i=1,2,…,n, let Ezi be the subgraph of K1,4,n induced by five edges incident with the vertex zi. We will easily get the following formula:(2)K1,4,n=XY∪XZ∪YZ=XY∪∪i=1nEzi.Lemma 1 (see [19]).
crK1,4,n=Z5,n+2n/2=nn−1 for any n≥1.Lemma 2 (see [24]).
crK5,n\e=n−1n−2 for any n≥1.Lemma 3 (see [13, 25]).
crS3∪K1+nK1=Z5,n+n/2 for any n≥1.Lemma 4.
For an edgee in complete tripartite graph K1,4,n, then(3)crK1,4,n\e≤Z5,n+n2,e∈XY,Z5,n+2n2−n2+1,e∈XZ,Z5,n+n2−n2+1,e∈YZ.Proof.
LetD be an optimal drawing of K5,n having Z5,n crossings due to Zarankiewicz [17]. In the drawing, we place the vertices of K5,n at coordinators 0,i and j,0 where −2≤i≤3, −n/2≤j≤n/2, and i,j≠0. Then, we join 0,i to j,0 with straight line segment.
Next, we join the edges ofK1,4=xyi,1≤i≤4 as shown in Figure 1, and an optimal drawing of the complete tripartite graph K1,4,n is obtained. Let us denote the drawing by D′. It is not difficult to see that crD′K1,4,n=crK1,4,n=Z5,n+2n/2. In the following, we obtain the graph K1,4,n\e together with its drawing from D′.(i)
Ife∈XY. By deleting the edge e=xy1 from D′, then a drawing of K1,4,n\exy is obtained. We can easily check that there are n/2 crossings on the edge of xy1. Therefore, we can verify that(4)crK1,4,n\exy≤Z5,n+2n2−n2=Z5,n+n2.(ii)
Ife∈XZ. Then, by deleting the edge of e=xzn/2, we can obtain a drawing of K1,4,n\exz. Likewise, the responsibility of the edge xzn/2 is 2n/2−1. So, we can obtain that(5)crK1,4,n\exy≤Z5,n+2n2−2n2−1=Z5,n+2n2−n2+1.(iii)
Ife∈YZ. In the optimal drawing of K5,n, which have Z5,n crossings given by Zarankiewicz, we reconnect the edges of K1,4=xyi,1≤i≤4, as shown in Figure 2. And then, by deleting the edge of e=y1z1, a drawing of K1,4,n\eyz is obtained. Let us denote the drawing by D′. Then, one can verify that the responsibility of the edges K1,4 and y1z1 is n and 2n/2−1+1, respectively. Therefore, we have(6)crK1,4,n\eyz≤Z5,n+n−2n2−1−1=Z5,n+n2−n2+1.
Combined with the above three cases, this completes the proof.Figure 1
A good drawing ofK1,4,n\exz.Figure 2
A good drawing ofK1,4,n\eyz.Theorem 1.
For any edgeexy in complete tripartite graph K1,4,n, where exy∈XY, then(7)crK1,4,n\exy=Z5,n+n2.Proof.
It is not difficult to know thatK1,4,n\exy contains a subgraph that is isomorphic to S3∪K1+nK1. And it was shown from Lemma 3 that crS3∪K1+nK1=Z5,n+n/2. Thus, crK1,4,n\exy≥crS3∪K1+nK1=Z5,n+n/2. The reverse inequalities are confirmed by Lemma 4. This completes the proof.Theorem 2.
For any edgeeyz in complete tripartite graph K1,4,n, where eyz∈YZ, then(8)crK1,4,n\eyz=Z5,n+n2−n2+1.Proof.
At first, according to Lemma4, we have crK1,4,n\eyz≤Z5,n+n/2−n/2+1, and Theorem 2 is true if the equality holds. For n=1 since K1,4,1\eyz is planar graph, therefore, crK1,4,1\eyz=0≥Z5,1+1/2−1/2+1=0 is true. Now, we suppose that crK1,4,m\eyz≥Z5,m+m/2−m/2+1 for any positive integer 2≤m≤n−1.
LetD be an optimal drawing of graph K1,4,n\eyz, which satisfies crDK1,4,n\eyz=crK1,4,n\eyz=c. Without loss of generality, we say eyz=y1z1. By deleting the edges of Ez1 from drawing D, the graph K1,4,n−1 is obtained. Hence, we get that(9)rDz1≤c−crK1,4,n−1.
Likewise, for anyi=2,3,…,n, we have the following that(10)rDzi≤c−crK1,4,n−1\eyz.
Otherwise, by deleting the edges ofEzi for any i=2,3,…,n, we obtain the graph which is isomorphic to K1,4,n−1\eyz and has less than crK1,4,n−1\eyz crossings. Therefore, from (9) and (10), summing up for 1≤i≤n, we can obtain that(11)2c=∑i=1nrDbi≤c−crK1,4,n−1+n−1c−crK1,4,n−1\eyz.
Thus, we simplify and conclude that(12)crK1,4,n\eyz=c≥n−1crK1,4,n−1\eyz+crK1,4,n−1n−2.
Finally, combining with inductive hypothesis and Lemma1, we have that(13)crK1,4,n\eyz≥Z5,n+n2−n2+1.
Thus, the proof of Theorem2 is finished.Theorem 3.
For any edgeexz in complete tripartite graph K1,4,n, where exz∈XZ, then(14)crK1,4,n\exz=Z5,n+2n2−n2+1.Proof.
From Lemma4, we can get that crK1,4,n\exz≤Z5,n+2n/2−n/2+1. Thus, Theorem 3 is true; we need only to prove that crφK1,4,n\exz≥Z5,n+2n/2−n/2+1 for any drawing φ of K1,4,n\exz.
Without losing generality, we assume that under the drawingφ of K1,4,n\exz, the clockwise order of these four images φxyi around φx is φxy1⟶φxy2⟶φxy3⟶φxy4. And we assume exz=xz1. Thus, the graph K1,4,n\exz has an additional n−1 edges xzi incident with x2≤i≤n. Let A1,A2,A3,A4 denote the sets of all those images xzi, each of which places in the angle αi is formed between φxyi and φxyi+1, where the indices are read modulo 4 (see Figure 3(a)). We note that A1+A2+A3+A4=n−1. Further more, we see that in the plane R2, there exists a circular neighborhood around φx such that Nφx,ε=s∈R2:s−φx≤ε, where ε is a positive number small enough such that for any other edge yizji=1,2,3,4;j=1,2,…,n of K1,4,n\exz not incident with x, φyizj∩Nφx,ε=∅. Next, we divide two cases to discuss.Figure 3
A drawingφ′ of K5,n+1\e obtained from φK1,4,n\exz.Case 1.
assumen−1 is odd. Thus, we have A1≠A3 or A2≠A4. Otherwise, n−1=∑I=14Ai=2A1+A2; this contradicts the fact that n−1 is odd. Without loss of generality, we assume A1≠A3, and more precisely, let A3≥A1+1. In the following, we produce the graph K5,n+1\e together with its drawing φ' by three steps.Step 1.
Add a new vertexzn+1 in some location of φxy2∩Nφx,ε.Step 2.
For all1≤i≤4, delete the partition of φxyi lying in Nφx,ε (do not delete the vertex zn+1).Step 3.
Connectzn+1 to each vertex in φx,φy1,…,φy4 in such a way as described in Figure 3(b).
Thus, we obtain a drawingφ' of the graph K5,n+1\e from the drawing φ of K1,4,n\exz. It is easy to obtain that(15)crφ′K5,n+1\e=crφK1,4,n\exz+2A1+A2+A4,≤crφK1,4,n\exz+n−2.
With the help ofcrK5,n+1\e=nn−1 by Lemma 2, we have that(16)crφK1,4,n\exz≥crφ′K5,n+1\e−n+2≥nn−1−n+2≥Z5,n+2n2−n2+1.Case 2.
assumen−1 is even. We consider arbitrarily a pair of numbers A1 and A3 or A2 and A4. Without losing generality, we say A1 and A3, again we say A1≤A3. Completely analogously to Case 1 above, we can get a drawing φ' of graph K5,n+1\e such that(17)crφ′K5,n+1\e=crφK1,4,n\exz+2A1+A2+A4≤crφK1,4,n\exz+n−1.
Now, applyingcrK5,n+1\e=nn−1, we obtain the following that(18)crφK1,4,n\exz≥crφ'K5,n+1\e−n+1≥nn−1−n+1≥Z5,n+2n2−n2+1.
Thus, by the arguments derived in Cases 1 and 2, we have shown thatcrφK1,4,n\exz≥Z5,n+2n/2−n/2+1 for any drawing φ of K1,4,n\exz. This completes the proof.
Therefore, from Theorems1–3, we can get the following corollary immediately.Corollary 1.
For an edgee in complete tripartite graph K1,4,n, then(19)crK1,4,n\e=Z5,n+n2,e∈XY,Z5,n+2n2−n2+1,e∈XZ,Z5,n+n2−n2+1,e∈YZ.


## 3. Crossing Number ofK2,3,n\e

In graphK2,3,n, let X,Y,Z be the vertex partition, where X=x1,x2, Y=y1,y2,y3, Z=z1,z2,…,zn. We denote XY, XZ, YZ be the subgraphs of K2,3,n induced by EXY,EXZ,EYZ, respectively. Clearly, XY≅K2,3. For i=1,2,…,n, let Ezi be the subgraph of K2,3,n induced by five edges incident with zi. We can easily get that(20)K2,3,n=XY∪XZ∪YZ=XY∪∪i=1nEzi.Lemma 5 (see [18]).
crK2,3,n=Z5,n+n for any n≥1.Lemma 6 (see [26]).
crK2,3\e+nK1=Z5,n+n/2 for any n≥1.Lemma 7.
For an edgee in complete tripartite graph K2,3,n, then(21)crK2,3,n\e≤Z5,n+n2,e∈XY,n2−2n+2,e∈XZ,n2−2n+1,e∈YZ.Proof.
LetD be an optimal drawing of K5,n having Z5,n crossings due to Zarankiewicz [17]. In the drawing, we place the vertices of K5,n at coordinators 0,i and j,0 where −2≤i≤3,−1/2≤j≤1/2 and i,j≠0. Then, we join 0,i to j,0 with straight line segment.
Next, we join the edges ofK2,3=xiyj,1≤i<j≤3, as shown in Figure 4, and thus an optimal drawing of the complete tripartite graph K2,3,n is obtained. Let us denote the drawing by D′. We can easily check that crDK2,3,n=crK2,3,n=Z5,n+n. In the following, we obtain the graph K2,3,n\e together with its drawing from D′.(i)
Ife∈XY. By deleting the edge e=x2y2 from D′, then a drawing of K2,3,n\exy is obtained. It is easily checked that there are n/2 crossings on the edge of x2y2. Therefore, we can verify that (22)crK2,3,n\exy≤Z5,n+n−n2=Z5,n+n2.(ii)
Ife∈XZ. We can get a drawing of K2,3,n\exz by deleting the edge e=x1zn/2 from D′. Obviously, the responsibility of the edge of x1zn/2 is 2n/2−1. So, we have(23)crK2,3,n\exz≤Z5,n+n−2n2−1=n2−2n+2.(iii)
Ife∈YZ. The drawing of K2,3,n\eyz can be obtained by deleting the edge e=y1z1 from D′. We note that the edge y1z1 crosses with the edges YZ∪x2y2 exactly 2n/2−1+1 times. Thus, we obtain that(24)crK2,3,n\eyz≤Z5,n+n−2n2−1−1=n2−2n+1.
Therefore, according to the above analysis, we have completed the proof.Figure 4
An optimal drawing ofK2,3,n.Theorem 4.
For any edgeexy in complete tripartite graph K2,3,n, where exy∈XY, then(25)crK2,3,n\exy=Z5,n+n2.Proof.
It is not difficult to know thatK2,3,n\exy is isomorphic to K2,3\e+nK1. And it was shown by Lemma 6 that crK2,3\e+nK1=Z5,n+n/2. Thus, crK2,3,n\exy≥crK2,3\e+nK1=Z5,n+n/2. The reverse inequalities are confirmed by Lemma 7. Hence, the proof is done.Theorem 5.
For any edgeexz in complete tripartite graph K2,3,n, where exz∈XZ, then(26)crK2,3,n\exz=n2−2n+2.Proof.
Without loss of generality, letexz=x1zn. Therefore, according to (4), we note that(27)K2,3,n\exz=XY∪∪i=1n−1Ezi∪Ezn=K2,3∪∪i=1n−1Ezi∪Ezn.
At first, we can obtain by Lemma7 that crK2,3,n\exz≤n2−2n+2. It is not difficult to know that K2,3,1\exz contains a subgraph which is isomorphic to K3,3 and K2,3,2\exz contains a subgraph which is isomorphic to K3,4. Thus, we have crK2,3,1\exz≥1 and crK2,3,2\exz≥2, so the theorem is established for n=1 and 2. Now, we suppose that n≥3 and that crK2,3,k\exz≤k2−2k+2 for any 3≤k≤n−1. We will derive contradiction to prove the reverse inequality. We assume to contrary that K2,3,n/exz has a good drawing D such that(28)crDK2,3,n\exz≤n2−2n+1.
In the subsequent proof process, we always deduce some contradictions to∗. We first have the following claims.Claim 1.
crDEzi,Ezj≥1 for all i,j=1,2,…,n−1, and i≠j.Proof.
Otherwise, without loss of generality, letcrDEz1,Ez2=0. According to Lemma 5, crK2,3,2=2 implies that crDK2,3,Ez1∪Ez2≥2. As Ez1∪Ez2∪Ezn isomorphic to K5,3\e, and it was shown by Lemma 2 that crK5,3\e=2. Thus, crDEzn,Ez1∪Ez2≥2. The known fact that crK3,5=4 implies that crDEzi,Ez1∪Ez2≥4 for all i=3,4,…,n−1. Therefore, we have(29)crDK2,3,n\exz=crDK2,3∪∪i=3nEzi∪Ez1∪Ez2≥crDK2,3,n−2\exz+crDK2,3∪∪i=3nEzi,Ez1∪Ez2≥Z5,n−2+n−2−2n−22+2+4+4n−3=n2−2n+2.
Clearly, this contradicts to∗.Claim 2.
crDK2,3+crDK2,3,∪i=1nEzi≤n−1.Proof.
Otherwise, we havecrDK2,3+crDK2,3,∪i=1nEzi≥n. As ∪i=1nEzi is isomorphic to K5,n\e, and it was proved by Lemma 2 that crK5,n\e=n−1n−2. Thus, we obtain(30)crDK2,3,n\exz=crDK2,3∪∪i=1n−1Ezi∪Ezn≥crDK2,3+crDK2,3,∪i=1n−1Ezi∪Ezn+crD∪i=1n−1Ezi∪Ezn≥n+n−1n−2=n2−2n+2.
This also contradicts to∗.
Furthermore, we have the following claim.Claim 3.
There exists a vertexzi1≤i≤n−1 such that crDK2,3,Ezi=0.Proof.
IfcrDK2,3=0, then the good drawing of K2,3 induced by D divides the plane into three quadrangular regions ωy1,y2, ωy2,y3, and ωy3,y1 depending on which two of the vertices y1,y2,y3, and y4 are placed on the corresponding boundary. Thus, under the drawing of K2,3, we have crDK2,3,Ezn≥1 and crDK2,3,Ezi≥1 for all i=1,2,…,n−1. In other words, the edges of K2,3 are crossed at least n times by the subgraphs ∪i=1n−1Ezi; this contradicts with Claim 2.
IfcrDK2,3≥1, combining together with Claim 2, we can obtain that crDK2,3,∪i=1n−1Ezi≤n−2. This forces that there exists a vertex zi1≤i≤n−1 such that crDK2,3,Ezi=0. Thus, Claim 3 is proved.
Now, we continue to prove the theorem. By Claim 3, without loss of generality, we assumecrDK2,3,Ez1=0. Thus, there is a disk such that the five vertices of K2,3 are all placed on the boundary of disk. We assume the vertex z1 placed in the external of the disk, and the edges of K2,3 are all placed in the inner side of the disk. It is easy to obtain that two drawing of K2,3∪Ez1 as shown in Figure 5.
In Figure5, except for the region which marked with α, each of regions contains at most two vertices of K2,3 in its boundary. Hence, we obtain that crDK2,3∪Ez1,Ezi≥3. When zi is placed in the region α, we have crDK2,3∪Ez1,Ezi≥2, if and only if crDK2,3,Ezi=2 and the equality crDEz1,Ezi=0 holds. This together with Claim 1 implies that crDK2,3∪Ez1,Ezi≥3.
Moreover, each region contains at most three vertices ofK2,3 in its boundary in Figure 5. Thus, crDK2,3∪Ez1,Ezn≥1. Therefore, it follows from crDK2,3∪Ez1=1, ∪i=1n−1Ezi≅K5,n\e, and the assumption of the theorem that(31)crDK2,3,n\exz=crDK2,3∪Ez1∪∪i=2n−1Ezi∪Ezn≥crDK2,3∪Ez1+crDK2,3∪Ez1,∪i=2n−1Ezi∪Ezn+crD∪i=2n−1Ezi∪Ezn≥1+3n−2+1+n−2n−3=n2−2n+2.
Clearly, this contradicts to∗.
In summary, the hypothesis is not true, and the proof is done.
Using the method completely similar to Theorem5, we can get the following Theorem 6. Thereby, the proof process of Theorem 6 is omitted here.Figure 5
Two drawings ofK2,3∪Ez1.Theorem 6.
For any edgeeyz in complete tripartite graph K2,3,n, where eyz∈YZ, then(32)crK2,3,n\eyz=n2−2n+1.SinceK2,3,n\exz is isomorphic to K3,n\e+2K1, thus we have the following corollary.Corollary 2.
crK3,n\e+2K1=n2−2n+1,n≥1.Together with Theorems4–6, we can get the following corollary immediately.Corollary 3.
For an edgee in complete tripartite graph K2,3,n, then(33)crK2,3,n\e=Z5,n+n2,e∈XY,n2−2n+2,e∈XZ,n2−2n+1,e∈YZ.


## 4. Conclusion

The problem crossing numbers of graphs are originated in a practical application, whose theory has been widely applied in many fields. However, determining the crossing numbers of graphs are NP-complete. Because of its difficulty, the research progress is slow. In this paper, according to the structural characteristics of complete multipartite graph, using “drawing restriction method,” “embedding method,” and “point degree local modification method,” we determine the exact value of crossing numbers ofK1,4,n\e and K2,3,n\e. These results are an in-depth work of TBFP, which will be beneficial to the further study of crossing numbers and its applications.Finally, we give some conjecture and open problems.Conjecture 1.
crK6,n\e=Z6,n−2n−1/2 for n≥1.Problem 1.
For an edgee in complete tripartite graph K1,5,n, K2,4,n, and K3,3,n. Then what are the precise values of crossing numbers of K1,5,n\e, K2,4,n\e, and K3,3,n\e?



---

*Source: 4550953-2022-06-07.xml*