The search functionality is under construction.

The search functionality is under construction.

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*)) ≤ 2*k*^{4} - *k*^{3} - 4*k*^{2} - 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*(*n*^{2}*k*^{2n-2}) when *n* ≥ *k* and *O*(*nk*^{2n-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

Antoine BOSSARD

Kanagawa University

Keiichi KANEKO

Tokyo University of Agriculture and Technology

Frederick C. HARRIS, JR.

University of Nevada

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.

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*)) ≤ 2*k*^{4} - *k*^{3} - 4*k*^{2} - 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*(*n*^{2}*k*^{2n-2}) when *n* ≥ *k* and *O*(*nk*^{2n-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*)) ≤ 2*k*^{4} - *k*^{3} - 4*k*^{2} - 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*(*n*^{2}*k*^{2n-2}) when *n* ≥ *k* and *O*(*nk*^{2n-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*)) ≤ 2*k*^{4} - *k*^{3} - 4*k*^{2} - 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*(*n*^{2}*k*^{2n-2}) when *n* ≥ *k* and *O*(*nk*^{2n-1}) otherwise.

ER -