- Start and end nodes of a given arc
- A node incidence list for every node
- Information which edges are directed

There is a universal interface to retrieve information about the skeleton. That is, dense graphs also have a logical view of incidence lists, but no according memory representation. Only the skeleton of graphs with a sparse representation can be manipulated.

Observe that Orientation(2i) and Orientation(2i+1) are the same, and this tells whether the edge i is directed. In that case, Blocking(2i) returns false but Blocking(2i+1) returns true. The latter method is used to generalize optimization methods from directed to mixed graphs (e.g. for minimum spanning arborescence or max-cut). It is not applied by shortest path methods which occasionally operate on implicitly modified digraphs (residual networks).

- StartNode(i) and EndNode(i) give the two nodes which are connected by the arc i with the identity StartNode(i)==EndNode(i^1).
- First(v) gives either NoArc or an arc index such that StartNode(First(v))==v.
- Right() can be used to enumerate all incidences of a particular node, including the blocking backward arcs. One has StartNode(Right(i))==StartNode(i).

For dense graphs, all these method internally calculate node indices from arc indices or vice versa. Sparse graphs have incidence lists represented in memory.

Node incidence lists cannot only be searched by directly calling First() and Right(). There are proxy objects, called investigators, maintaining an incidence list pointer (i.e. an arc index) for every graph node.