Other > E-books
Textbook in PDF format
The theory of planar graphs was first discovered in 1736 by Euler when he found his important formula relating the numbers of vertices, edges and faces of polyhedrons, which can be represented by planar graphs. Since that time numerous results have been obtained on planar graphs. One of the most outstanding results is Kuratowski's theorem which gives a criterion for a graph to be planar. Another example is the famous four-color theorem: every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color. In recent years, planar graphs have attracted computer scientists' interest, and a lot of interesting algorithms and complexity results have been obtained for planar graphs. For example, Hopcroft and Tarjan have reported on a linear time algorithm which tests the planarity of a graph.
Recently it appeared to us that the time was ripe to collect and organize the many results on planar graphs, which have been our research topics for these ten years. In our opinion the theory and algorithms are complementary to each other in the research of planar graphs. For example, Hopcroft and Tarjan's algorithm was motivated by Kuratowski's theorem although it was not explicitly used in the algorithm. On the other hand many theoretic results have been obtained from the algorithmic view point. Thus we have tried to include most of the important theorems and algorithms that are currently known for planar graphs. Furthermore we have tried to provide constructive proofs for theorems, from which algorithms immediately follow. Most of the algorithms are written in Pidgin PASCAL in a manner that will make their adaptation to a practical programming language relatively easy. They are all efficient, and most of them are the best known ones; the complexities are linear or O(n log n).
A glance at the table of contents will provide an outline of the topics to be discussed. The first two chapters are introductory in the sense that they provide the foundations, respectively, of the graph theoretic notions and algorithmic techniques that will be used in the book. Experts in graph theory or algorithms may skip Chapters 1 or 2. The remaining chapters discuss the topics on planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independent set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. The topics reflect the authors' favor as graph theorists and computer scientists. The chapters are structured in such a way that the book will be suitable as a textbook in a course on algorithms, graph theory, or planar graphs. In addition, the book will be useful for computer scientists and graph theorists at the research level. An extensive reference section is also included.
Preface
Acknowledgments
Graph Theoretic Foundations
Algorithmic Foundations
Planarity Testing and Embedding
Drawing Planar Graphs
Vertex-Coloring
Edge-Coloring
Independent Vertex Sets
Listing Subgraphs
Planar Separator Theorem
Hamiltonian Cycles
Flows in Planar Graphs
References
Index
