- Membership
- Publications
- Meetings
- Competitions
- Community
- Programs
- Students
- High School Teachers
- Faculty and Departments
- Underrepresented Groups
- MAA Awards
- MAA Grants

- News
- About MAA

Publisher:

Chapman & Hall/CRC

Publication Date:

2006

Number of Pages:

779

Format:

Hardcover

Edition:

2

Series:

Discrete Mathematics and Its Applications 35

Price:

84.95

ISBN:

1-58488-505-X

Category:

Textbook

[Reviewed by , on ]

William J. Satzer

02/24/2006

This is a huge book, almost 200 pages longer than the already massive first edition. One is tempted to call it "Everything You Wanted to Know about Graph Theory but Were Afraid to Ask". Nonetheless, *Graph Theory and Its Applications* is a very good textbook.

What makes it good is strong rapport with the reader, a coherent organization, and consistently clear exposition. The book is aimed at a diverse set of readers. Courses based on this book could be directed toward computer science (concentrating on data structures and algorithms), operations research (focusing on discrete optimization), or mathematics (emphasizing the algebraic and topological aspects). The text is most appropriate for advanced undergraduates or beginning graduate students. Since it is essentially self-contained, it could also be used profitably for self-study.

The basics of graph theory (structure and representation, trees, connectivity, optimal transversal of graphs) are covered well in the first six chapters. Planarity and Kuratowski's theorem are discussed in depth in Chapter 7 where the authors begin their treatment of topological graph theory. There is a strong chapter on network flows and applications, and another on digraph models. Later chapters take up more advanced topics (enumeration, voltage graphs, design of nonplanar layouts). New to this second edition of the text are treatments of Ramsey theory as well as random graphs, an especially hot topic now.

Notable attractive features of the text are breakout boxes with pseudo-code for all significant algorithms (as well as suggestions for specific software implementations), hundreds of examples of graphs carefully integrated with the text, a glossary of terms with each chapter (especially useful in this terminology-heavy field), and a ton of exercises — many with solutions or hints. My only real quibble is that the pages all seem too full. No doubt this was in effort to keep the number of pages down in an already large book. But one wishes for more white space.

Of course, there are practical applications too. If you are ever caught in a maze consisting of tunnels and rooms, use Tarry's algorithm (page 189) to escape, using a variation on depth-first search. Never backtrack through a tunnel unless there is no alternative, and never go through a tunnel a second time in the same direction.

Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.

INTRODUCTION TO GRAPH MODELS

Graphs and Digraphs

Common Families of Graphs

Graph Modeling Applications

Walks and Distance

Paths, Cycles, and Trees

Vertex and Edge Attributes: More Applications

STRUCTURE AND REPRESENTATION

Graph Isomorphism Revised!

Automorphisms and Symmetry Moved and revised!

Subgraphs

Some Graph Operations

Tests for Non-Isomorphism

Matrix Representation

More Graph Operations

TREES Reorganized and revised!

Characterizations and Properties of Trees

Rooted Trees, Ordered Trees, and Binary Trees

Binary-Tree Traversals

Binary-Search Trees

Huffman Trees and Optimal Prefix Codes

Priority Trees

Counting Labeled Trees: Prüfer Encoding

Counting Binary Trees: Catalan Recursion

SPANNING TREES Reorganized and revised!

Tree-Growing

Depth-First and Breadth-First Search

Minimum Spanning Trees and Shortest Paths

Applications of Depth-First Search

Cycles, Edge Cuts, and Spanning Trees

Graphs and Vector Spaces

Matroids and the Greedy Algorithm

CONNECTIVITY Revised!

Vertex- and Edge-Connectivity

Constructing Reliable Networks

Max-Min Duality and Menger's Theorems

Block Decompositions

OPTIMAL GRAPH TRAVERSALS

Eulerian Trails and Tours

DeBruijn Sequences and Postman Problems

Hamiltonian Paths and Cycles

Gray Codes and Traveling Salesman Problems

PLANARITY AND KURATOWSKI'S THEOREM Reorganized and revised!

Planar Drawings and Some Basic Surfaces

Subdivision and Homeomorphism

Extending Planar Drawings

Kuratowski's Theorem

Algebraic Tests for Planarity

Planarity Algorithm

Crossing Numbers and Thickness

DRAWING GRAPHS AND MAPS Reorganized and revised!

The Topology of Low Dimensions

Higher-Order Surfaces

Mathematical Model for Drawing Graphs

Regular Maps on a Sphere

Imbeddings on Higher-Order Surfaces

Geometric Drawings of Graphs New!

GRAPH COLORINGS

Vertex-Colorings

Map-Colorings

Edge-Colorings

Factorization New!

MEASUREMENT AND MAPPINGS New Chapter!

Distance in Graphs New!

Domination in Graphs New!

Bandwidth New!

Intersection Graphs New!

Linear Graph Mappings Moved and revised!

Modeling Network Emulation Moved and revised!

ANALYTIC GRAPH THEORY New Chapter!

Ramsey Graph Theory New!

Extremal Graph Theory New!

Random Graphs New!

SPECIAL DIGRAPH MODELS Reorganized and revised!

Directed Paths and Mutual Reachability

Digraphs as Models for Relations

Tournaments

Project Scheduling and Critical Paths

Finding the Strong Components of a Digraph

NETWORK FLOWS AND APPLICATIONS

Flows and Cuts in Networks

Solving the Maximum-Flow Problem

Flows and Connectivity

Matchings, Transversals, and Vertex Covers

GRAPHICAL ENUMERATION Reorganized and revised!

Automorphisms of Simple Graphs

Graph Colorings and Symmetry

Burnside's Lemma

Cycle-Index Polynomial of a Permutation Group

More Counting, Including Simple Graphs

Polya-Burnside Enumeration

ALGEBRAIC SPECIFICATION OF GRAPHS

Cyclic Voltages

Cayley Graphs and Regular Voltages

Permutation Voltages

Symmetric Graphs and Parallel Architectures

Interconnection-Network Performance

NON-PLANAR LAYOUTS Reorganized and revised!

Representing Imbeddings by Rotations

Genus Distribution of a Graph

Voltage-Graph Specification of Graph Layouts

Non KVL Imbedded Voltage Graphs

Heawood Map-Coloring Problem

APPENDIX

Logic Fundamentals

Relations and Functions

Some Basic Combinatorics

Algebraic Structures

Algorithmic Complexity

Supplementary Reading

BIBLIOGRAPHY

General Reading

References

SOLUTIONS AND HINTS New!

INDEXES

Index of Applications

Index of Algorithms

Index of Notations

General Index

- Log in to post comments