Journal or Book Title
Journal of Graph Theory
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 Gwith edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound . to . 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.
Wiley Periodicals, Inc.
Gethner, Ellen; Hogben, Leslie; Lidicky, Bernard; Pfender, Florian; Ruiz, Amanda; and Young, Michael, "On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs" (2016). Mathematics Publications. 54.