Embedding area of d‐way shuffle graph on a VLSI model

AbstractAn important problem in the design of a VLSI chip is that of determining how much area is taken to embed a graph G into a planar grid when the VLSI chip is modeled using a graph called a planar grid and a circuit is expressed by a graph G representing wiring connections between elements. Discussed for various graphs will be the upper and lower bounds on the planar grid area into which a graph is embedded. In this paper we consider the problem of embedding a d‐way shuffle graph into a planar grid, using a model which has been extended so that a graph with degree five or more can be embedded. d‐way shuffle graphs are also of theoretical interest since data exchange can be done in high speed like a shuffle exchange graph and a CCC. By using a relationship between the number of crossings of a graph and its area, we show that for the infinite number of d and k an area proportional to dk+1/k)2 is required to embed a dk‐vertex, d‐way shuffle graph. Using this result, the previous lower bound of the area can be improved. Further, for an embedding of a graph G we present an embedding method of G which uses a graph with a known embedding area. By using this result we show that if d is a power of 2, a dk‐vertex, d‐way shuffle graph can be embedded in an area proportional to (dk+1/2)2.