Algorithmic graph problems constitute approximately one third of all the problems in this catalog. Further, several problems from other sections can be formulated strictly in terms of graphs. Identifying the name of a graph-theoretic invariant or problem is one of the primary skills of a good algorist. Indeed, this catalog will tell you exactly how to proceed as soon as you figure out your particular problem's name.
We have partitioned the bulk of the algorithmic graph problems in this book between this and the subsequent section. Here, we deal only with problems for which there exist efficient algorithms to solve them. As there is often more than one way to model a given application, it makes sense to look here before proceeding on to the harder formulations.
The algorithms presented here have running times that grow slowly with the size of the graph. We adopt throughout the standard convention that n refers to the number of vertices in a graph, while m is the number of edges.
Although graphs are combinatorial objects, describing a binary relation on a set of objects, graphs are usually best understood as drawings. Beyond just the problems of visualization, many interesting graph properties follow from the nature of a particular type of drawing, such as planar graphs. In this chapter, we also present a variety of different problems and algorithms associated with graph drawing.
Most advanced graph algorithms are difficult to program. However, good implementations are often available if you know where to look. The best single source is LEDA, discussed in Section , although faster special-purpose codes exist for many problems.
Books specializing in graph algorithms include: