Approximation algorithms for geometric embeddings in the plane with applications to parallel processing problems

Given an undirected graph G with N vertices and a set P of N points in the plane, the geometric embedding problem consists of finding a bijection from the vertices of G to the points in the plane which minimize the sum total of edge lengths of the embedded graph. Fast approximation algorithms are given for embedding d-dimensional grids in the plane within a factor of O(log N) times optimal cost for d>2 and O(log²N) for d=2. It is shown that any embedding of a hypercube, butterfly, or shuffle-exchange graph must be within an O(log N) factor of optimal cost. When the points of P are randomly distributed or arranged in a grid, a polynomial-time algorithm that can embed arbitrary weighted graphs in these points with cost within an O(log²N) factor of optimal is given. It is shown how the algorithms developed for geometric embeddings can be used to give O(log²N) times optimal solutions to problems of performance optimization for parallel processors