ALCOMFT-TR-03-84

Josep Díaz, Mathew Penrose, Jordi Petit and Maria Serna
Approximating Layout Problems on Random Geometric Graphs
Barcelona. Work packages 2, 4 and 5. November 2003.

Abstract: 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 whenever they are closer than some given parameter. The layout problems that we consider are: Bandwidth, Minimum Linear Arrangement, Minimum Cut Width, Minimum 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 graphs. Then, we present two heuristics that, almost surely, turn to be constant approximation algorithms for our layout problems on random geometric graphs. In fact, for the Bandwidth and Vertex Separation problems, these heuristics are asymptotically optimal. Finally, we use the theoretical results in order to empirically compare these and other well-known heuristics.

Postscript file: ALCOMFT-TR-03-84.ps.gz (272 kb).