Planar Graphs

Graph Theoretic Foundations. Some Basic Definitions. Planar Graphs. Euler's Formula. Kuratowski's Theorem. Dual Graphs. Bounds for Planar Graphs. Algorithmic Foundations. What is an Algorithm? Machine Model and Complexity. NP-Complete. Data Structure and Graph Representation. Exploring a Graph. Planarity Testing and Embedding. Planarity Testing. Embedding Algorithm. Drawing Planar Graphs. Convex Drawing. Convex Testing. Example. Vertex-Coloring. Proof of Five-Coloring Theorem and 0(n 2 ) Algorithm. Batch Processing Algorithm. Sequential Processing Algorithm. Edge-Coloring. Algorithm COLOR. Algorithm ALCOLOR. Edge-Coloring Multigraphs. Independent Vertex Sets. Approximation Algorithm. Baker's Algorithm. Listing Subgraphs. Arboricity and Efficient Edge-Searching. Listing Triangles. Listing Quadrangles. Listing Maximal Cliques. Planar Separator Theorem. Applications of the Planar Separator Theorem. Maximum Matching. Minimum Vertex Cover. Hamiltonian Cycles. Proof of Tutte's Theorem. Algorithm and 0(n 2 ) Bound. Hamiltonian Walk. Flows in Planar Graphs. Definition of Multicommodity Flows. Planar Single-Commodity Flow. Multicommodity Flows for C 1 . Multicommodity Flows for C a . Bibliography. Index.