| Straight-Line Grid Drawings of Planar Graphs Contributor(s): Karim, MD Rezaul (Author) |
|
 |
ISBN: 3639174860 ISBN-13: 9783639174861 Publisher: VDM Verlag OUR PRICE: $60.53 Product Type: Paperback Published: December 2009 |
| Additional Information |
| BISAC Categories: - Computers | Information Technology |
| Physical Information: 0.32" H x 6" W x 9" (0.46 lbs) 136 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: 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. |