Statistical Properties of the Placement of a Graph

Abstract

The statistics of placing vertices of a graph on a square array of points is developed for several classes of graphs. Distribution functions for the lengths to be associated with edges are given. A lower bound is devised for the average value within each class of the lowest placement distance of a graph. For one class of graphs, this is compared with values devised from actual placements of a random set of representatives, and it can be seen that the lower bound devised here comes close to the actual value for the average minimum distance. A highly approximate formula is derived for one class of graphs (the simplest of the three classes considered) and is given by (19): \[ {\tilde{\mathcal{L}}}_{\min } = N\frac{{C^{1/2 - C /2N}}}{{e^{1 - C/2N}}} \] where C is the number of vertices in the graph and N is the number of edges, while ${\tilde{\mathcal{L}}}_{\min} $ is our lower bound on the average of the minimum distance of the placements of the graphs. The relationship to the quadratic assignment problem is shown, as well as how the theory can be extended to cover the case of net routing.