On the General Graph Embedding Problem With Applications to Circuit Layout

We consider the problem of embedding one graph in another, where the cost of an embedding is the maximum distance in the target graph separating vertices that are adjacent in the source graph. An important special case, know as the bandwidth minimization problem, is when the target graph is a path. This author has shown that for random graphs having bandwidth at most k, a well-known heuristic produces solutions having cost not more than 3k with high probability. This paper considers generalizations of this heuristic and analyzes their performance in other classes of target graphs. In particular, we describe a heuristic that for random graphs having a cost k embedding in a rectangular grid, produces embeddings having cost not more than 3k with high probability. This problem has applications to laying out circuits in the plane so as to minimize the lengths of the longest wire. Similar results can be obtained for multi-dimensional grids, as well as triangular and hexagonal grids