A possibly new representation of DAGs I had an idea for a way of representing DAGs, it's very easy to explain:

Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must be greater than each of A's respective integers.

For example the graph:

A o - &gt; o C
    \
     -&gt; 
B o - &gt; o D


Could be represented by:

A = [0,1]
B = [1,0]
C = [1,2]
D = [2,2]


I have a few questions:


Has such a representation been thought up before?
If no, would you help me to design an algorithm that generates the arrays of integers given a DAG?
[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result. 

Note that your representation will only be capable of representing transitively-closed DAGs, i.e.&nbsp;partial orders; and this representation is a previously-studied one for partial orders. For instance, a paper by Mihalis Yannakakis shows that determining whether a partial order (equivalently, a transitively-closed digraph) has such a representation is NP-complete for n&nbsp;&ge;&nbsp;3, but feasible if n&nbsp;&le;&nbsp;2.



Also, because the representation describes transitively closed DAGs, the body of research on the Transitive Closure problem is a reasonable place to look for related representations. My original response described a representation which, as it turned out, was strictly less general than the representation in terms of vectors. However, your representation has some similarities to the tree-cover representation of transitively closed DAGs (see Efficient management of transitive relationships in large data and knowledge bases: also described briefly in this article).


Without loss of generality, if the DAG has more than one 'source' (vertex with in-degree 0), add a virtual 'root' which can reach all of the sources. The entire DAG then has a spanning tree.
For each vertex, define an interval [&nbsp;av&nbsp;,&nbsp;bv&nbsp;] to each vertex v, in such a way that the interval at each node contains the intervals of all its descendants. (For instance, the upper bound bv for each v can be taken to be the post-fix order of the vertex in the tree; the lower bound av is the minimum of these post-fix values for the sub-tree.)
To represent directed edges which are not in the tree, each node keeps a list of the intervals of the different nodes which are reachable from it. (For any given sub-tree which is reachable from a given node, it suffices to record the interval belonging to the root of that sub-tree.)


Thus, the in-bound edges of each vertex is represented by the single interval [&nbsp;av&nbsp;,&nbsp;bv&nbsp;]&nbsp;, and its outbound edges are represented by a union of disjoint intervals which strictly contain the intervals of vertices that it can reach.

Some observations:


The vector representation is related to the interval nesting condition by using higher dimensional "intervals". Without loss of generality, the length n of the array xv at each vertex is even (by buffering with a final dummy co-ordinate if needed). Let m&nbsp;=&nbsp;n/2. Partition the coefficients as
$$ \mathbf x^v \;=\; [ \;a^v_1 \;,\; \ldots \;,\; a^v_m \;;\; c^v_1 \;,\; \ldots \;,\; c^v_m \;] $$
For each 1&nbsp;&le;&nbsp;j&nbsp;&le;&nbsp;m&nbsp;, let $$ U_j = \left( \max_v \;\; a^v_j \right) + \left( \max_v \;\; c^v_j \right). $$ Then, we may define for each node an m-fold cartesian product of intervals,
$$ I^v \;=\; [\;a^v_1\;,\; U_1-c^v_1 \;] \times \cdots \times [\;a^v_m\;,\; U_m-c^v_m \;]. $$
Two such "$m$-dimensional intervals" nest if and only if the corresponding vectors have the appropriate ordering relations. It is trivial to verify that the intervals nest only if the corresponding vectors are ordered; for the converse, we depend on none of the coefficients in the graph being larger than the corresponding bounds Uj&nbsp;.
It is not clear to me whether the representation by vectors and by tree-covers are efficiently interconvertible; however it is easy to show that the case n&nbsp;=&nbsp;2 corresponds exactly to the representation of directed trees in terms of tree-covers (i.e.&nbsp;the two representations are efficiently and reversibly inter-convertible, essentially by the technique I described above). Thus, the dimension may in some sense correspond to how tree-like the digraph is.