pictorial representation of pre and post ordering for edge types I am reading chapter 3 Decomposition of Graphs of Algorithms by Dasgupta, Papadimitriou &amp; Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, back and cross edges. I have pasted the image of the area I am unclear on.
I am assuming that u is the node/vertex we see first and then we see v later. Comparing to the 2nd image showing the definitions on a graph, I am taking u as node A.
What I don't get is the order for the other 2 back and cross edges. What I have is

u v u v for back edge.
u u v v for cross edge.

Essentially the order is flipped with u and v in what the textbook has. Could someone clarify why this is the case with the image below.


I read this answer but I came out more confused with the explanation.
Surprisingly I was able to correctly identify the pre and post numbers in this figure in the textbook. It is the letters u and v that have me confused.
&quot;I am assuming that $u$ is the node/vertex we see first and then we see $v$ later.&quot; That is a wrong assumption, which makes that summarizing table unintelligible.
The right assumption consists of two parts.

We are given a directed graph that contains $(u,v)$, the edge from $u$ to $v$.
We have just completed one depth first search (DFS) on that graph, which has discovered both $u$ and $v$.

Given the assumption above, that table lists the correspondence between the &quot;pre/post ordering for $u$ and $v$&quot;, and the &quot;edge type&quot; of $(u,v)$. Please note that I rephrase &quot;pre/post ordering for $(u,v)$&quot; as in the table to &quot;pre/post ordering for $u$ and $v$&quot;, since the meaning of &quot;$(u,v)$&quot;, the edge from $u$ to $v$ does not fit the former phrase exactly.

The first row, &quot;$\stackrel{[}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{]}{u}\ $ Tree/forward&quot; says that $u$'s discovery time and departure time enclose $v$'s discovery time and departure iff $(u,v)$ is a tree edge or a forward edge. $u$ is visited first in this case.
The second row, &quot;$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{]}{v}\ $ Back&quot; says that $v$'s discovery time and departure time enclose $u$'s discovery time and departure time iff $(u,v)$ is a back edge. $v$ is visited first in this case.
The third row, &quot;$\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\ $ Cross&quot; says that $v$'s discovery time and departure time are before $u$'s discovery time and departure time iff $(u,v)$ is a cross edge. $v$ is visited first in this case.

Neither do we assume $u$ is visited first nor do we assume $v$ is visited first. The node that is visited first on each row of that table is, of course, the node that appears first from the left on that row.

Exercise (as given in the book). With the same assumption, &quot;do you see why no other orderings are possible?&quot; For example, why is &quot;$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{v}\,\stackrel{]}{u}$&quot; not possible? why is &quot;$\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}$&quot; not possible?