Next: Connected Components Up: A Catalog of Algorithmic Previous: Satisfiability

# Graph Problems: Polynomial-Time

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:

• Even [Eve79a] - This is a good book on graph algorithms, fairly advanced, with a particularly thorough treatment of planarity-testing algorithms.
• Ahuja, Magnanti, and Orlin [AMO93] - While purporting to be a book on network flows, it covers the gamut of graph algorithms with emphasis on operations research. Strongly recommended.
• van Leeuwen [vL90a] - A 100+ page survey on research results in graph algorithms, this is the best source to determine what is known in algorithmic graph theory.
• McHugh [McH90] - A more elementary but comprehensive treatment of basic graph algorithms, including parallel algorithms.

Next: Connected Components Up: A Catalog of Algorithmic Previous: Satisfiability

Algorithms
Mon Jun 2 23:33:50 EDT 1997