Is there a structure similar to a graph but which includes a sense of direction, like north, west, east, south?

Question

I understand that graphs do not have any notion of "facing", that is, a sense of relative or cardinal directions. Using a conventional graph, it's not possible to say "go left at vertex A," as far as I understand it.

However, I'm wondering if there is any such structure — that is, one which can represent vertices and edges, as well as a sense of what one might refer to as direction or orientation.

Suppose I'm standing on vertex A. Vertex A is connected to vertex Z, with several vertices in-between, some of which have edges which lead elsewhere. Assume I'm forbidden from naming the intermediate vertices/edges. How can I describe the path from A to Z?

Answer 1

One possibility is to use a rotation system. Since that link is a little technical, here's a slightly more basic way to think of a rotation system that may be more suitable to your purposes. A rotation system is a function $\Phi$ that assigns to each vertex $v \in V(G)$ an ordered sequence consisting of all neighbors of $v$ in $G$. A rotation system is usually thought of as representing an embedding of a graph in a particular surface, so that if $\Phi(v) = (v_1, v_2, \dots, v_i)$, then the edges $(v,v_1),(v,v_2),\dots, (v, v_i)$ are embedded in that order clockwise around $v$ in the surface.

There are then a couple ways you could define paths using the rotation system for $G$:

1. A path can be described by a sequence consisting of two vertices and integers. For example, $(u,v,1,4)$ could describe the path in $G$ beginning with the edge $(u,v)$, followed by the edge $(v,w)$ that is $1$ edge clockwise of $(u,v)$ at $v$, and finally the edge that is $4$ edges clockwise of $(v,w)$ at $w$.

2. Or, you could think of the first element $u$ of $\Phi(v)$ as a special vertex, so that you could think of $(u,v)$ as being oriented "north", say. Then a path could be described as a vertex together with a sequence of integers. For example, $(u,1,4,2)$ could represent the path beginning at $u$, going to the first element $v$ in the sequence $\Phi(u)$, then the fourth element $w$ in $\Phi(v)$, and finally the second element of $\Phi(w)$.

Answer 2

If you want there to be only one way to "go left" (etc) at a given vertex, what you're looking for is an automaton, for example a finite state machine.

This is a structure with states (vertices) and named transitions, and a map $\{\mathrm{states}\} \times \{\mathrm{transitions}\} \rightarrow \{\mathrm{states}\}$. That is, at any state, if you specify the next transition (e.g. "go left") it takes you to the appropriate next state. (If you don't want there to be a way to go left at a given state, you would simply have it transition to the same state.)

This could be represented by a directed graph with vertices for the states and edges labeled by the transitions such that at every vertex there's precisely one outgoing edge for each transition. Then to specify a path starting at any vertex, you simply name the start vertex and the sequence of transitions and this uniquely specifies a path.

---

If you merely wish to record which direction an edge is going, you could certainly make a labeled graph (perhaps a directed one) where the labels are directions, but this sounds less like what you want.