In a directed graph an edge is adjacent to its source and in an undirected graph it is adjacent to its source and target. Note that these two operations are not exactly inverse to each other. The reversal information of an edge e is accessed through G . In other words, reversal deserves its name. We call a directed graph bidirected if for every edge of G the reversed edge also belongs to G and we call a bidirected graph a map if all edges have their reversal information defined.
Maps are the data structure of choice for embedded graphs.
Each edge is contained in some face cycle and face cycles are pairwise disjoint. Let f be the number of face cycles, n be the number of nodes, m be the number of edges, and let c be the number of connected components. The genus is zero if and only if the map is planar, i.e., there is an embedding of G into the plane such that for every node v the counter-clockwise ordering of the edges around v agrees with the cyclic ordering of v 's adjacency list. If a graph G is a map the faces of G can be constructed explicitly by G . Note that any update operation performed on G invalidates the list of faces.