Approximating layout problems on random geometric graphs

In this paper, we study the approximability of several layout problems on a family of random geometric graphs. Vertices of random geometric graphs are randomly distributed on the unit square and are connected by edges wheneve r they are closer than some given parameter. The layout problems that we co nsider are bandwidth, minimum linear arrangement, minimum cut width, minimu m sum cut, vertex separation, and edge bisection. We first prove that some of these problems remain NP-complete even for geometric graphs. Afterwards, we compute lower bounds that hold, almost surely for random geometric grap hs. Then, we present two heuristics that, almost surely, turn out to be con stant approximation algorithms for our layout problems on random geometric graphs. In fact, for the bandwidth and vertex separation problems, these he uristics are asymptotically optimal. Finally, we use the theoretical result s in order to empirically compare these and other well-known heuristics. (C ) 2001 Academic Press.