IMPROVED BOUNDS FOR THE CROSSING NUMBER OF THE MESH OF TREES
Robert J. Cimikowski, Imrich Vrt’o · Journal of Interconnection Networks · 2003
Improved bounds for the crossing number of the mesh of trees graph, Mn, are derived. In particular, we derive a new lower bound of [Formula: see text] which improves on the previous bound of Leighton [11] by a constant factor, and an upper bound of [Formula: see text]. In addition, we construct drawings of Mn which achieve the upper bound number of crossings. We also prove that the crossing number of M4 is 4.