IEICE TRANSACTIONS on Fundamentals
On the Crossing Number of a Torus Network
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 n ≥ k 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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Antoine BOSSARD, Keiichi KANEKO, Frederick C. HARRIS, JR., "On the Crossing Number of a Torus Network" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 1, pp. 35-44, January 2023, doi: 10.1587/transfun.2021EAP1144.
Abstract: 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 n ≥ k and O(nk2n-1) otherwise.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2021EAP1144/_p
Copy
@ARTICLE{e106-a_1_35,
author={Antoine BOSSARD, Keiichi KANEKO, Frederick C. HARRIS, JR., },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Crossing Number of a Torus Network},
year={2023},
volume={E106-A},
number={1},
pages={35-44},
abstract={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 n ≥ k and O(nk2n-1) otherwise.},
keywords={},
doi={10.1587/transfun.2021EAP1144},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - On the Crossing Number of a Torus Network
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 35
EP - 44
AU - Antoine BOSSARD
AU - Keiichi KANEKO
AU - Frederick C. HARRIS
AU - JR.
PY - 2023
DO - 10.1587/transfun.2021EAP1144
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2023
AB - 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 n ≥ k and O(nk2n-1) otherwise.
ER -
English
