The incidence graph is a data structure for storing and manipulating graphs.
A graph is a triple , where and are finite sets, called the vertices and the edges, respectively, and is called the incidence function. The incidence function tells for each edge its end-vertices, and whether the edge is directed (1) or not (0). If an edge is directed, then the first element and the second element of denote the origin vertex and the destination vertex, respectively. This generality is required to represent all of undirected graphs, directed graphs, and mixed graphs, possibly combined with self-loops and multi-edges. A labeled graph is a graph together with labeling functions and , where and are arbitrary sets, called the vertex labels and the edge labels, respectively. A graph is called directed, if all its edges are directed. A graph is called simple if it has at most one edge between any two vertices, and no loop-edges.
The incidence graph data structure has the following properties:
| Task / Property | Complexity |
|---|---|
| Insert / remove an isolated vertex. | |
| Insert / remove an edge. | |
| Provide a list (and number) of vertices. | |
| Provide a list (and number) of edges. | |
| Provide a list (and number) of incoming edges incident to a vertex. | |
| Provide a list (and number) of outgoing edges incident to a vertex. | |
| Provide a list (and number) of undirected edges incident to a vertex. | |
| Find the end-vertices of an edge. | |
| Space |
Here is the number of vertices, and is the number of edges.
Graph Theory and its Applications, 2nd. ed., Jonathan L. Gross, Jay Yellen, 2005.