Routing on Triangles, Tori and Honeycombs

The standard n \Theta n torus consists of two sets of axes: horizontal and vertical ones. For routing h-relations, the bisection bound gives a lower bound of h \Delta n=4. Several algorithms nearly matching this bound have been given. In this paper we analyze the routing capacity of modified tori: tessellations of the plane with triangles or hexagons and tori with added diagonals. On some of these networks the ratio of routing capacity and degree is higher than for ordinary tori, even though they are as easily constructed. Hence, they may constitute more cost effective alternatives. For networks with n 2 PUs, we get the following results: on a torus of hexagons, node degree 3, h-relations are performed in 0:37 \Delta h \Delta n steps; on a torus of triangles, node degree 6, in 0:13 \Delta h \Delta n; and on a torus with added diagonals, node degree 8, in h \Delta n=12. The latter result matches the bisection bound for this network. Even faster is the routing on a torus of hexagons w..