On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs
Ellen Gethner, Leslie Hogben, Bernard Lidický, Florian Pfender, Amanda Ruiz, Michael Young · Journal of Graph Theory · 2016
Abstract The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to urn:x-wiley:03649024:media:jgt22041:jgt22041-math-0004 and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.