The search functionality is under construction.
The search functionality is under construction.

On the Crossing Number of a Torus Network

Antoine BOSSARD, Keiichi KANEKO, Frederick C. HARRIS, JR.

  • Full Text Views

    0

  • Cite this

Summary :

Reducing the number of link crossings in a network drawn on the plane such as a wiring board is a well-known problem, and especially the calculation of the minimum number of such crossings: this is the crossing number problem. It has been shown that finding a general solution to the crossing number problem is NP-hard. So, this problem is addressed for particular classes of graphs and this is also our approach in this paper. More precisely, we focus hereinafter on the torus topology. First, we discuss an upper bound on cr(T(2, k)) the number of crossings in a 2-dimensional k-ary torus T(2, k) where k ≥ 2: the result cr(T(2, k)) ≤ k(k - 2) and the given constructive proof lay foundations for the rest of the paper. Second, we extend this discussion to derive an upper bound on the crossing number of a 3-dimensional k-ary torus: cr(T(3, k)) ≤ 2k4 - k3 - 4k2 - 2⌈k/2⌉⌊k/2⌋(k - (k mod 2)) is obtained. Third, an upper bound on the crossing number of an n-dimensional k-ary torus is derived from the previously established results, with the order of this upper bound additionally established for more clarity: cr(T(n, k)) is O(n2k2n-2) when nk and O(nk2n-1) otherwise.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.1 pp.35-44
Publication Date
2023/01/01
Publicized
2022/08/05
Online ISSN
1745-1337
DOI
10.1587/transfun.2021EAP1144
Type of Manuscript
PAPER
Category
Graphs and Networks

Authors

Antoine BOSSARD
  Kanagawa University
Keiichi KANEKO
  Tokyo University of Agriculture and Technology
Frederick C. HARRIS, JR.
  University of Nevada

Keyword