Straight-Line grid drawings of planar graphs with sub-Quadratic area

Abstract

This thesis deals with area efficient straight-line drawings of planar graphs. It is well known that a planar graph of n vertices admits a straight-line grid drawing on a grid of area O(n2 ). A lower bound of n(n2) on the area-requirement for straight-line grid drawings of certain planar graphs are also known. In this thesis, we introduce some classes of planar graphs that admit straight-line grid drawing with sub-quadratic area. We introduce "doughnut graphs", a subclass of 5-connected planar graphs as well as 3-outerplanar graphs, which admits a straight-line grid drawing on a grid of area O(n). We introduce a subclass of 4-connected planar graphs that admits straight-line grid drawing with linear area. We also introduce a subclass of outerplanar graphs, which we call "label-constrained outerplanar graphs," that admits straight-line grid drawings with O(n log n) area. We give linear-time algorithms to find such drawings. We also give linear-time algorithms for recognition of these classes of graphs. We have studied the k-partition problem for newly introduced classes of graphs, and found some interesting results for "doughnut graphs." We give a linear-time algorithm for finding k-partition of a "doughnut graph." We also study the topological properties of these classes of planar graphs for finding their suitable applications. We propose the class of "doughnut graphs" as a promising class of interconnection networks due to its regularity, smaller diameter, maximal fault tolerance, recursive structure and a very simple efficient routing scheme.