Planar graphs: Theory and algorithms (Q1210706)

Origins of the theory of planar graphs can be traced back to 1736 when Euler discovered his famous formula relating the numbers of vertices, edges and faces of a polyhedron. Since that time, numerous results have been obtained for planar graphs, and they have motivated an extensive research also in other branches of graph theory and combinatorics. Recently, moreover, there has been a great deal of interest in algorithms concerning planar graphs, and the past 15 years have witnessed an important development in this field. As stated in the Preface, it appeared to the authors that the time was ripe to collect and organize the enormous amount of results on planar graphs. The selection presented in this monograph has been predetermined by trying to link systematically the purely theoretical results on planar graphs with algorithms. In the authors' opinion, these two aspects are complementary to each other in the research of planar graphs. This view is supported e.g. by the fact that the authors provide constructive proofs for theorems, from which algorithms immediately follow. Most of the algorithms in the text are the best known ones. They are written in Pidgin PASCAL and are easily adaptable to a practical programming language. The first two chapters review foundations of both graph theory (with emphasize on planarity) and algorithmic techniques used in the book. The remaining chapters deal with theoretical as well as algorithmic aspects of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independent set, subgraph listing, planar separator theorems, Hamiltonian cycles, and single- or multicommodity flows in planar graphs. For many of the topics included, the present monograph is the first complete treatment in book form. The book will be useful not only for students but also for specialists in graph theory and computer science which are interested in the theory and algorithms for planar graphs. Contents: Preface. - Acknowledgements. - 1. Graph theoretic foundations: Introduction; Some basic definitions; Planar graphs; Euler's formula; Kuratowski's theorem; Dual graphs; Bounds for planar graphs. - 2. Algorithmic foundations: What is an algorithm; Machine model and complexity; NP-complete; Data structure and graph representation; Exploring a graph; Depth-first search; Breadth-first search. - 3. Planarity testing and embedding: Introduction; Planarity testing; Embedding algorithm. - 4. Drawing planar graphs: Introduction; Convex drawing; Convex testing; Example. - 5. Vertex-coloring: Introduction; Proof of the five-coloring theorem and the \(O(n^ 2)\) algorithm; Batch processing algorithm. - 6. Edge-coloring: Introduction; Algorithm COLOR; Algorithm ALCOLOR; Edge-coloring multigraphs. - 7. Independent vertex sets: Introduction; Approximation Algorithm; Baker's algorithm. - 8. Listing subgraphs: Introduction; Arboricity and efficient edge-searching; Listing triangles; Listing Quadrangles; Listing maximal cliques. - 9. Planar Separator Theorem: Introduction; Preliminary; Planar separator theorem; Applications of the planar separator theorem; Maximum matching; Minimum vertex cover. 10. Hamiltonian cycles: Introduction; Proof of Tutte's theorem; Algorithm and \(O(n^ 2)\) bound; Hamiltonian walk. - 11. Flows in planar graphs: Introduction; Definition of multicommodity flow; Multicommodity flows for \(C_ 1\) (Preliminary; Feasibility; Algorithm DELTAFLOW; Algorithm MULTIFLOW1; Time and space of MULTIFLOW1); Multicommodity flows for C (Feasibility; Algorithm MULTIFLOW2; Refinement and complexity). - References. - Index.