Vertex ordering and partitioning problems for random spatial graphs

By Mathew D. Penrose.

Given an ordering of the vertices of a graph, let the induced weight for an edge be the separation of its end-points in the ordering. Layout problems involve choosing the ordering to minimize a cost functional such as the sum or maximum of the edge-weights. We give growth rates for the costs of some of these problems on supercritical percolation processes and supercritical random geometric graphs, obtained by placing vertices randomly in the unit cube and joining them whenever at most some threshold distance apart.

Annals of Applied Probability, 10, 517-538 (2000).