ABSTRACT
This chapter reviews the basic concepts and notations for graph theory. It connects these concepts to image processing and analysis from a conceptual level and discusses implementation details. A graph represents a set of elements and a set of pairwise relationships between those elements. A graph may be represented by one of several different common matrices. A matrix representation may provide efficient storage, but each matrix representation may also be viewed as an operator that acts on functions associated with the nodes or edges of a graph. Several computer representations of graphs can be considered. The data structures used to represent graphs can have a significant influence on the size of problems that can be performed on a computer and the speed with which they can be solved. Computer vision and image processing have a long history of using graph models, but these models have been increasingly dominant representations in the recent literature.
