Our objective in writing this book is to present the theory of graphs from an algorithmic viewpoint. We present the graph theory in a rigorous, but informal style and cover most of the main areas of graph theory. The ideas of surface topology are presented from an intuitive point of view. We have also included a discussion on linear programming that emphasizes problems in graph theory. The text is suitable for students in computer science or mathematics programs.

Graph theory is a rich source of problems and techniques for programming and data structure development, as well as for the theory of computing, including NP-completeness and polynomial reduction.

This book could be used a textbook for a third or fourth year course on graph algorithms which contains a programming content, or for a more advanced course at the fourth year or graduate level. It could be used in a course in which the programming language is any major programming language (e.g., C, C++, Java). The algorithms are presented in a generic style and are not dependent on any particular programming language.

The text could also be used for a sequence of courses like ``Graph Algorithms I'' and ``Graph Algorithms II''. The courses offered would depend on the selection of chapters included. A typical course will begin with Chapters 1, 2, 3, and 4. At this point, a number of options are available.

A possible first course would consist of Chapters 1, 2, 3, 4, 6, 8, 9, 10, 11, and 12 , and a first course stressing optimization would consist of Chapters 1, 2, 3, 4, 8, 9, 10, 14, 15, and 16. Experience indicates that the students consider these substantial courses. One or two chapters could be omitted for a lighter course.

We would like to thank the many people who provided encouragement while we wrote this book, pointed out typos and errors, and gave useful suggestions. In particular, we would like to convey our thanks to Ben Li and John van Rees of the University of Manitoba for proofreading some chapters.

William Kocay
Donald L. Kreher