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.
