Straight-Line Grid Drawings of Planar Graphs

Md. Rezaul Karim received his Ph.D. in 2008 from the Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh. He completed M. Tech. from the Indian Institute of Technology (IIT), Kharagpur, India. He has been working as a faculty in the Department of Computer Science and Engineering, University of Dhaka, Bangladesh from 1998.

A graph is an abstract structure that is used to model information. Many real-world situations can conveniently be described by means of graphs. Smaller area of a drawing increases the readability of the drawing. Compact drawing of a circuit is preferable for VLSI fabrication since a compact drawing helps us to avoid wasting of valuable wafer space. This book deals with area efficient straight-line drawings of planar graphs. We have introduced 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(nlog n) area. We give linear-time algorithms to find such drawings. We also give linear-time algorithms for recognition of these classes of graphs.