Other > E-books
Textbook in PDF format
This book deals with theories and algorithms for drawing planar graphs. Graph drawing has appeared as a lively area in computer science due to its applications in almost all branches of science and technology. Many researchers have concentrated their attention on drawing planar graphs for the following reasons:
drawings of planar graphs have no edge crossings, and look nice;
drawings of planar graphs have practical applications in VLSI floor-planning and routing, architectural floorplanning, displaying RNA structures in bioinformatics, etc.; and
algorithms for drawing planar graphs can be successfully used for drawing a nonplanar graph by transforming it into a similar planar graph.
During the last two decades numerous results have been published on drawing planar graphs. For example, in 1990 it was shown that every planar graph of n vertices has a straight-line drawing on a grid of area O(n²). This result solved the open question for about four decades whether a planar graph has a straight line drawing on a grid of a polynomial area. Many algorithms have been developed to produce drawings of planar graphs with different styles to fulfill different application needs. While developing these algorithms, many elegant theories on the properties of planar graphs have been discovered, which have applications in solving problems on planar graphs other than graph drawing problems. On the other hand, many established graph theoretic results have been successfully used to solve graph drawing problems.
Recently, it appeared to us that a systematic and organized book containing these many results on planar graph drawings can help students and researchers of computer science to apply the results in appropriate areas. For example, we observed that people working with VLSI floorplanning by rectangular dual did not notice Thomassen's result on rectangular drawings of plane graphs. In our opinion the theory and algorithms are complementary to each other in the research of planar graph drawings. We have thus tried to include in the book most of the important theorems and algorithms that are currently known for planar graph drawing. Furthermore, we have tried to provide constructive proofs for theorems, from which algorithms immediately follow
