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).