Abstract:

In the literature, five families of optimal circulant graphs of degree four with a rectangular L-shape of tessellation of graphs on the plane $Z^2$ are known. The rectangular (mesh-connected) pattern of tessellation of the graph of intermodular connections allows an efficient arrangement of chips in networks on a chip -- with a minimum number of intersections of connections and their minimum length, independent of the number of nodes, and also an optimal algorithm for finding the shortest paths in terms of the number of operations.
In this paper, a new method for obtaining families of circulants with given scalability and optimality properties is found. Six series of new infinite families of optimal circulant graphs of degree four with a rectangular $L$-shape of laying graphs on the plane and a minimum diameter are obtained. The domains of existence of such series are considered. Analytical formulas for specifying the parameters of laying families of graphs on the plane are found, which can be used in organizing routing algorithms in networks-on-chip.