Home

My Ph.D. Thesis

Does Cubicity Help to Solve Problems? pdf file

Table of Contents  

Abstract

Preface

1. Introduction

1.1. Motivation
1.2. Thesis Overview and Statement of Results

2. Cubic Graphs

2.1. Introduction
2.2. Construction of Cubic Graphs
2.2.1. H-reduction and H-expansion
2.2.2. Transforming a Cubic Graph into Another
2.2.3. Transformation of a General Graph into a Cubic Graph
2.3. Classical Graph Theory Results
2.3.1. Coloring Problems
2.3.2. Matching Problems
2.3.3. Counting Problems
2.3.4. Cycles Problems
2.3.5. Subgraphs Problems

3. Orthogonal Drawing

3.1. Introduction
3.2. A Sequential Algorithm
3.2.1. Introduction
3.2.2. Drawing Biconnected Graphs
3.2.3. Drawing Connected Graphs
3.2.4. Experimental Results
3.3. A Parallel Algorithm
3.3.1. Introduction
3.3.2. Description of the Algorithm
3.3.3. Complexity Measures
3.4. 3D-Drawing
3.4.1. Introduction
3.4.2. Lower Bounds
3.4.3. Upper Bounds

4. Interconnection Networks

4.1. Introduction
4.2. A Tight Layout of the Butterfly Network
4.2.1. Introduction
4.2.2. The Upper Bound on the Layout Area
4.2.3. The Lower Bound on the Layout Area
4.3. On Trivalent Cayley Networks
4.3.1. Introduction
4.3.2. Optimal Layout of a TCIN
4.3.3. A Shortest Routing Algorithm

5. Approximation Algorithms

5.1. Introduction
5.2. MIDS in Bounded Degree Graphs
5.2.1. Introduction
5.2.2. MIDS in At Most Cubic Graphs
5.2.3. MIDS in Bounded Degree Graphs

6. Conclusions and Open Problems

Glossary

Bibliography

Home