ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 14 (2018) 329-344 https://doi.org/10.26493/1855-3974.1236.4d7 (Also available at http://amc-journal.eu) A note on the thickness of some complete bipartite graphs* * Siwei Hu, Yichao Chen t Department of Mathematics, Hunan University, 410082 Changsha, China Received 22 November 2016, accepted 17 July 2017, published online 19 September 2017 The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. Determining the thickness for the complete bipartite graph is an unsolved problem in graph theory for over fifty years. Using a new planar decomposition for K4k-i,ik (k > 4), we obtain the thickness of the complete bipartite graph Kn,n+4, for n > 1. Keywords: Planar graph, thickness, complete bipartite graph. Math. Subj. Class.: 05C10 1 Introduction In this paper, all graphs are simple. A graph G is denoted by G = (V, E) where V(G) is the vertex set and E(G) is the edge set. A complete graph is a graph in which any two vertices are adjacent. A complete graph on n vertices is denoted by Kn. A complete bipartite graph is a graph whose vertex set can be partitioned into 2 parts, such that every edge has its ends in different parts and every two vertices in different parts are adjacent. We use KPl,P2 to denote a complete bipartite graph in which the ith part contains p vertices, for i = 1, 2. The thickness t(G) of a graph G is the minimum number of planar subgraphs into which G can be decomposed [14]. It is a classical topological parameter of a graph and has many applications, for instance, to graph drawing [12] and VLSI design [1]. Since deciding the thickness of a graph is NP-hard [9], it is very difficult to get the exact number of thickness for arbitrary graphs. Battle, Harary and Kodama [3] in 1962 and Tutte [13] in 1963 independently showed that the thickness of K9 and Kw equals 3. Beineke and *We are grateful to the two anonymous referees for their helpful comments. The second author is supported by the NNSFC under Grant No. 11471106. t Corresponding author. E-mail addresses: husiwei@hnu.edu.cn (Siwei Hu), ycchen@hnu.edu.cn (Yichao Chen) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 329 Ars Math. Contemp. 14 (2018) 267-284 Harary [4] determined the thickness of complete graph Kn for n ^ 4 (mod 6) in 1965, the remaining case was solved in 1976, independently by V.B. Alekseev and V.S. Gonchakov [2] and by J.M. Vasak [15]. For complete bipartite graphs, the problem has not been entirely solved yet. By constructing a planar decomposition of Km n when m is even, Beineke, Harary and Moon [5] determined the thickness of Km n for most values of m, n in 1964. Theorem 1.1. [5] For m < n, the thickness of the complete bipartite graph Km,n is t(Km,n) 2(m + n - 2) (1.1) except possibly when m and n are both odd and there exists an integer k satisfying n ' 2fc(m-2) ' (m-2k) We recall that the thickness of Kn n is also obtained in 1968 by Isao and Ozaki [11] independently. The following open problem is adapted from [7] by Gross and Harary. Problem 1.2. [See Problem 4.1 of [7]] Find the thickness of Km n for all m, n. Beineke, Harary and Moon [5] also pointed out that the smallest complete bipartite graph whose thickness is unknown is K17,21. From Euler's Formula, the thickness of K17,21 is at least 5. From Theorem 1.1, we need to determine the thickness of Km n for odd m, n. Since the difference between the two odd numbers is even, we only need to determine the thickness of Kn,n+2k for odd n and k > 0. In this paper, we start to calculate the thickness of Kn n+2k for some small values of k. Indeed, we determine the thickness of Kn n+4. Theorem 1.3. The thickness of Kn,n+4 is t(Knn+4)= j!\3, ifn < 2 ( n,n+4) \ , otherwise. The following corollary follows from Theorem 1.3. Corollary 1.4. The thickness of K17 21 is 5. We may refer the reader to [6, 10, 16] for more background on graph thickness. 2 The thickness of Kn,n+4 To begin with, we define two special graphs called the pattern graph and the kth-order nest graph. Then, we prove a new planar decomposition of K4fc-4 4fc. Finally, we prove the thickness of ^-3,4^1 and Kn,n+4. 2.1 The pattern graph Let U = {u1, u2} and Xn be a set of n vertices. A graph is said to be a pattern graph of order n + 2, denoted by G[u1 Xnu2], if it can be constructed by the following two steps. 1. Arrange the n vertices in a row, and put vertices u1, u2 on the above and below of n vertices, respectively. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 331 2. Join both u1 and u2 to the n vertices using straight lines. From the definition above, the pattern graph is a planar straight-line graph. Figure 1 illustrates the pattern graph G[u1Xnu2}. Remark 2.1. Unless explicitly mentioned, we always join vertices using straight lines in the drawings of the following proofs. Figure 1: The pattern graph G[u1Xnu2]. 2.2 The kth-order nest graph Let Uk = [uil ,ui2 ,...,uik },Vk = [vj1 ,vj2 ,...,vjk} and W2k+2 = [wh ,wh,..., whk+2}, we define a kth-order nest graph G[Uk,Vk, W2k+2] as follows: 1. Arrange 2k + 2 vertices wll, wl2,..., w;2fc+2 in a row. 2. For 1 < m < k, place vertices uim and vjm on the above and below of the row, respectively, and join them to wh, whm, w^+i, whm+2. Figure 2 illustrates a third-order nest graph G[U3, V3, W8], where U3 = {u1, u2, u3}, V3 = {vi, v2, V3} and W8 = {wi, w2,..., w8}. V3 Figure 2: The third-order nest graph G[U3, V3, W8]. 2.3 A new planar decomposition of K4k-3,4k+1, for k > 4 In this subsection, we shall construct a planar decomposition for the complete bipartite graph K4k-3j4k+1 with k planar subgraphs G1,G2,... ,Gk. Suppose that the vertex partition of K4k-3,4k+i is (X, Y), where X = {x1,x2,... ,X4k-3}, Y = {yo,y1,y2, ...,V4k }. 332 Ars Math. Contemp. 14 (2018) 267-284 2.3.1 The planar decomposition for K4k-4,4k Let the vertex partition of K4k-4j4k be (Xi, Yi), where Xi = jxi, x2,..., x4k-4}, Yi = {y0, yi,..., y4k-i}. In this subsection, all subscripts in y- are taken mod 4k. 1. In the graph Gj (1 < i < k), we arrange 4k vertices in a row, and divide the 4k vertices into two subsets L2k and R2k such that each subset contains 2k vertices according to the following steps. 2. In the graph Gj (1 < i < k - 1), we choose four vertices x4j-3, x4j-2, x4j-i, x4j from Xi and construct two pattern graphs G[x4j-3L2kx4j-i] and G[x4j-2R2k x4j]. Then we join both x4j-3 and x4j-i to the first vertex and the last vertex in R2k. Finally, we label the vertices in L-k and R-k as yi, y3, y5,..., y4k-i and y2i+6, y2i+8, y2i+i0,..., y2i+4k+4 in turn, respectively. 3. In the graph Gk, we label the vertices in L2k and R2k as yi, y3, y5,... y4k-i and y2,y4,..., y4k-2, y0, respectively. First, we construct a (k - 1)th-order nest graph G[Ufc-i, Vk-i, W2fc], where Ufc_i = {x2,x6,xio,... ,x4k-6} , Vk-i = {x4,x8, xi2,..., X4fc-4, } and W-k = {yi, y3, y5,..., y4k-i}. We join x4j-3 to y2i and y2j+2, for 1 < i < k - 1. Second, we construct a union of paths, if k is even, we join x4i-i to y2j+2k and y2j+2+2k, for 1 < i < k - 1; otherwise k is odd, we join x4i-i to y2i+2k-2 and y2i+2k, for 1 < i < k - 1. 4. In each graph Gj (1 < j < k - 1), we put x4j-2, x4j in the quadrangle x4j-3y4j+i x4j-iy4j+3, and join them to y4j+i and y4j+3, for 1 < i < j. We put the vertices x4i-2,x4i in the quadrangle x4j-3y4j-ix4j-iy4j+i, and join both x4j-2 and x4j to y4j-i and y4j+i, for j < i < k - 1. Next, we put x4j-3 in the quadrangle x4j-2y4j-2i+4x4jy4j-2i+6, and join x4j-3 to y4j-2i+4,y4j-2i+6, for 1 < i < j. We put x4i-3 in the quadrangle x4j-2y4j-2i+4kx4jy4j-2i+4k+2, and join x4j-3 to y4j-2i+4k ,y4j-2i+4k+2, for j < i < k - 1. For each i (1 < i < k - 1), we define a set Mj = {i + 1, i + 2,..., i + k - 2}. Suppose that m G Mj, if m < k - 1, we let j = m; otherwise, j = m - k + 1. (i) k is even. If i +1 < m < i+ ^-t-4, we put x4j-i in the quadrangle x4j-2y4m-2j+4 x4jy4m-2i+6, andjoin x4j-i to y4m-2i+4, y4m-2i+6. If i+ ^ + 1 < m < i + k-2, we put x4i-i in the quadrangle x4j-2y4m-2j+8x4j y4m-2i+io, andjoin x4j-i to y4m-2i+8, y4m-2i+i0. (ii) k is odd. If i +1 < m < i + , we put x4j-i in the quadrangle x4j-2y4m-2j+4 x4jy4m-2i+6, andjoin x4i-i to y4m-2i+4, y4m-2i+6. If i + ^ + 1 < m < i + k-2, we put x4i-i in the quadrangle x4j-2y4m-2j+8x4j y4m-2i+io, andjoin x4j-i to y4m-2i+8, y4m-2i+i0. Theorem 2.2. Let Gi, G2,..., Gk be the planar subgraphs obtained from steps 1, 2, 3 and 4 above, then {Gi, G2,..., Gk} is a planar decomposition of K4k-4 4k. Proof. From the constructions above, we have E(Gj) n E(Gj) = 0, for 1 < i = j < k. In order to prove that {Gi, G2,..., Gk} is a planar decomposition of K4k-4,4k, we need to show that E(Gi) U E(G2) U • • • U E(Gk) = E(K4k-4,4k). We denote dGi(v) as the degree of v in Gj, for 1 < i < k. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 333 By the construction above, Step 2 contributes to the degrees of v4i_3, v4i_i, v4i-2, and v4i in Gj by terms 2k + 2, 2k + 2,2k +1 and 2k + 1, respectively. In other words, we have do, (v4i-3) = dGi (v4j-1) = 2k + 2 and dGi («44-2) = dGi ) = 2k + 1. For 1 < i < k - 1, Step 3 contributes to dGfc(v4i-3),d0fc(v4i-1),d0fc(v4i-2) and dGfc (v4i) by terms 2,2, 3, and 3, respectively. For 1 < j < k - 1 and i = j, Step 4 contributes to each of dGj(v4i-3), dGj (v4i-1), doj (v4i-2) and do, (^) a term 2. In total, for 1 < i < k - 1 , we have k k k X^do,- (v4i-i) = do,- (v4i-3) = do, (v4i-3) + ^ doj («44-3) + dofc («44-3) j=i j=i i 4. Proof. From Theorem 2.2, Subsection 2.3.2 and Subsection 2.3.3, a planar decomposition of K4k-3,4k+i with k planar subgraphs Gi, G2,..., Gk is obtained. FromEuler's formula, we have "(4k - 3)(4k + 1)" t(K4k-3,4k + i) > k, 2(8k - 4) and so t(K4k-3,4k+i) = k. □ Example 2.4. By using the procedure above, the two planar decompositions of Ki7,2i (k = 5 is odd) and K2i,25 (k = 6 is even) are shown in Appendix A (See Figures 3-7) and Appendix B (See Figures 8-13), respectively. 334 Ars Math. Contemp. 14 (2018) 267-284 2.4 Proof of Theorem 1.3 From Theorem 1.1, the proof has two cases: Case 1: n = 4k — 3 (k > 0). When 1 < k < 3, it is routine to check that the theorem is true. For k > 4, 2k(4k-3-2) 4k-3-2k 4k + 1 + 2k-3 4k+1, thus, the thickness of K4fc_3j4fc+i k = can not be determined by Theorem 1.1. By Theorem 2.3, we have t(K4fc_3 4k+1) r ^ i. ' Case 2: n = 4k — 1 (k > 0). Since 4k — 1 and 4k + 3 are both odd and 4k + 3 = 2(fc + 1)(4fc-1-2) 4k-1-2(k+1) (See Lemma 1 of [5] for details), the thickness of K4fc_1j4fc+3 can be determined by Theorem 1.1, thus t(K„,„+4) = t(k4fc-1,4fc+3) (4k - 1)(4k + 3) 2(4k - 1+4k + 3 - 2) k+1 13 k +---- 2 16k n + 3" Summarizing the above, the theorem follows. 4 3 Conclusion In this paper, we determine the thickness for K„,„+4. The proof replies on a planar decomposition of K4fc-3,4fc+1 and the Theorem 1.1 of Beineke, Harary and Moon. We observe that our approach for the construction of a planar decomposition of K„,„+4 is the first step in finding a solution for Problem 1.2. From Theorem 1.1, the next classes of complete bipartite graphs whose thickness is unknown is K4k-1,4k+7, for k > 10. Furthermore, the new smallest complete bipartite graph whose thickness is unknown is K19,29. We hope that the construction here helps establish intuition and structure of the Problem 1.2. Another way of solving the Problem 1.2 is to find a new planar decomposition of Km,„, for odd m, n. Actually, using a new planar decomposition of the complete tripartite graph K1,g,n and a recursive construction, we also [8] obtained the thickness of Ks,t, where s is odd and t > (s-3)3(s-2). Now we split Problem 1.2 into the following two problems. Problem 3.1. Find the thickness of K„,„+4k for odd n and k > 2. Problem 3.2. Find the thickness of K„,„+4k+2 for odd n and k > 0. References [1] A. Aggarwal, M. Klawe and P. Shor, Multilayer grid embeddings for VLSI, Algorithmica 6 (1991), 129-151, doi:10.1007/bf01759038. [2] V. B. Alekseev and V. S. Goncakov, The thickness of an arbitrary complete graph, Mat. Sb. (N. S.) 101(143) (1976), 212-230, http://mi.mathnet.ru/eng/msb3 8 9 7. [3] J. Battle, F. Harary and Y. Kodama, Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962), 569-571, doi:10.1090/s0002-9904-1962-10850-7. [4] L. W. Beineke and F. Harary, The thickness of the complete graph, Canad. J. Math. 17 (1965), 850-859, doi:10.4153/cjm-1965-084-2. [5] L. W. Beineke, F. Harary and J. W. Moon, On the thickness of the complete bipartite graph, Proc. Camb. Phil. Soc. 60 (1964), 1-5, doi:10.1017/s0305004100037385. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 335 [6] L. W. Beineke and R. J. Wilson (eds.), Topics in Topological Graph Theory, volume 128 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2009, doi:10.1017/cbo9781139087223. [7] J. L. Gross and F. Harary, Some problems in topological graph theory, J. Graph Theory 4 (1980), 253-263, doi:10.1002/jgt.3190040302. [8] S. Hu and Y. Chen, The thickness of some complete tripartite graphs, preprint. [9] A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Camb. Phil. Soc. 93 (1983), 9-23, doi:10.1017/s030500410006028x. [10] P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs Combin. 14 (1998), 59-73, doi:10.1007/pl00007219. [11] I. Shirakawa, H. Takahashi and H. Ozaki, On the planar decomposition of a complete bipartite graph, SIAMJ. Appl. Math 16 (1968), 408-416, doi:10.1137/0116034. [12] I. G. Tollis, G. Di Battista, P. Eades and R. Tamassia, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, Upper Saddle River, New Jersey, 1999. [13] W. T. Tutte, The non-biplanar character of the complete 9-graph, Canad. Math. Bull. 6 (1963), 319-330, doi:10.4153/cmb-1963-026-x. [14] W. T. Tutte, The thickness of a graph, Indag. Math. (Proceedings) 66 (1963), 567-577, doi: 10.1016/s1385-7258(63)50055-9. [15] J. M. Vasak, The Thickness of the Complete Graph, Ph.D. thesis, University of Illinois at Urbana-Champaign, ProQuest Dissertations Publishing, 1976, https://search. proquest.com/docview/302820090. [16] Y. Yang, Remarks on the thickness of Kn>n>n, Ars Math. Contemp. 12 (2017), 135-144, https://amc-journal.eu/index.php/amc/article/view/82 3. 336 Ars Math. Contemp. 14 (2018) 267-284 A A planar decomposition {G1, G2, G3, G4, G5} for K17,2i Figure 4: The graph G2. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 337 33S Ars Math. Contemp. 14 (2G1S) 329-344 S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 339 B A planar decomposition {G1, G2, G3, G4, G5, G6} for K21,25 Figure 10: The graph G3. 340 Ars Math. Contemp. 14 (2018) 329-344 Figure 11: The graph G4. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 341 Figure 10: The graph G3. 342 Ars Math. Contemp. 14 (2018) 329-344 Figure 11: The graph G4. S. Hu and Y. Chen: A note on the thickness of some complete bipartite graphs 343 33S Ars Math. Contemp. 14 (2G1S) 329-344