2 Modeling Graphs

A number of different data structures provide useful representations of a graph $G$. Different representations of $G$ often lend themselves to specific applications. Indeed, the efficiency of graph algorithms often relies on the manner in which a graph is represented. For this reason, it may prove necessary to transform a graph from one representation to another to implement a complex series of graph operations. It can be shown that converting $G$ between representations requires no more than $O\left({|V|}^{2}\right)$ operations.