ALCOMFT-TR-01-157

Jordi Petit
Layout Problems
Barcelona. Work packages 2, 4 and 5. June 2001.

Abstract: This doctoral dissertation deals with algorithmic issues arising in the study of graph layout problems. Specifically, the following layout problems are considered: Minimum Linear Arrangement, Bandwidth, Cutwidth, Vertex Separation, Sum Cut, Modified Cut, Edge Bisection and Vertex Bisection. These problems represent an important class of hard problems with different applications in various disciplines.

We start with a survey trying to give a complete view of the current state of the art with respect to layout problems. We consider applications, complexity results, lower bounds, approximation algorithms and heuristics.

The first contribution is an experimental study on the Minimum Linear Arrangement problem. Several lower bounding methods and heuristics are presented, implemented and analyzed on a test suite of graphs. The results of the resulting benchmarking are used in order to design a new parallel heuristic to quickly discover better solutions. Latter, we develop some topics motivated by these experimental results.

The study of layout problems on G_n,p graphs is then considered. We show that, with overwhelming probability, several well known layout problems are approximable within a constant on these graphs. In fact, our results establish that the cost of any algorithm is within a constant factor of the optimal cost.

Afterwards, we undertake an study of layout problems on graphs with a geometrical structure. We show that Bandwidth, Cutwidth and Vertex Separation remain NP-complete even when restricted to grid graphs. We also give solutions for VertSepL, SumCutL, BandwidthL and VertBisL on square grids, and prove tight upper bounds for several layout problems on general grid graphs.

We then consider random grid graphs and random geometric graphs. We present convergence theorems that characterize the behavior of layout problems on subcritical random grid graphs and subcritical random geometric graphs. We present approximation algorithms that, for some layout problems, are asymptotically optimal for supercritical random geometric graphs. These results are strongly related to the BHH theorem and Karp's dissection algorithm for the TSP. We use these theoretical results to draw an experimental analysis to compare some popular heuristics for the Edge Bisection problem.

We then apply the framework developed to treat layout problems and geometric graphs to analyze several properties of faulty random geometric networks. The considered properties are Hamiltonicity, emulation and layout costs.

Finally, we present an analysis for some communication tree problems on several classes of random graphs. Approximation algorithms are obtained.

Advisor: Josep D\'\iaz.

The thesis is also available in PDF format (9.6 Mb).

Postscript file: ALCOMFT-TR-01-157.ps.gz (3517 kb).