Graph decomposition into cycles + edges consistent with a linear order over the vertices I'm interested in decomposing a graph $G$ into a set $\{H_1, \dots, H_n\}$ of cycles and edges of $G$, with an added twist. By decomposing $G$ I mean the usual notion that the $H_i$'s form a partition of $G$, i.e., $\bigcup_{i=1}^n H_i = G$ and $H_i\cap H_j = \emptyset$. For clarity, I identify the $H_i$'s and $G$ with the sets of their edges.
The twist is that I want to ensure that there exists a linear order $L$ over the vertices of $G$ that satisfies each subgraph $H_i$ in the decomposition. What I mean by this is the following (note that I write $xy$ for the edge $(x,y)$):

*

*if $H_i$ consists of a single edge $xy$, then $L$ satisfies $H_i$ if $x$ appears before $y$ in $L$, i.e., it holds that $L = \dots x\dots y\dots$;

*if $H_i$ is an $x_1\dots x_m$-cycle in $G$, i.e., $H_i = \{x_1x_2, \dots, x_{m-1}x_m, x_mx_1\}$, then $L$ satisfies $H_i$ if $L$ contains exactly $m-1$ of the comparisons in $H_i$.

To give a quick example, for the set of vertices $\{a,b,c,d,e\}$, the order $L = bcdea$ satisfies the subgraph $H = \{bd\}$, corresponding to an edge from $b$ to $d$, because $L$ orders $b$ and $d$ in the order specified by $H$; and $L$ also satisfies the $abc$-cycle $H' = \{ab, bc, ca\}$ on $a$, $b$, $c$, because it contains the comparisons $bc$ and $ca$, i.e., $L$ breaks the cycle in the most 'efficient' way, by sacrificing only one edge of $H'$.
Now, as an example of what I'm interested in, say we have the graph $G$:

One way to decompose $G$ into cycles and edges is to start with the $abc$-cycle $\{ab, bc, ca\}$ on $a$, $b$ and $c$, and add the remaining edge subgraphs $\{bd\}$, $\{da\}$, $\{ae\}$ and $\{ec\}$. However, this decomposition does not satisfy the extra consistency requirement I mentioned above: any linear order consistent with the edge-subgraphs would have to contain comparisons $bd$, $da$, $ae$ and $ec$ and, by virtue of transitivity, also $ba$ and $ac$, the only such linear order being $L = bdaec$. However, $L$ does not satisfy the $abc$-cycle since it flips two of its edges, i.e., $ab$ and $ac$.
On the other hand the decomposition of $G$ into the $abd$- and $aec$-cycle, plus the edge $bc$, works just fine: $L = abdec$. for instance, satisfies all the components of the decomposition.
My main interest at this point is in knowing whether such a decomposition exists for any graph $G$. Some intuitive procedures I've tried for the last couple of days, that I thought should work, have turned out not to. So at this point any hints to understanding the problem a bit better would be appreciated.
 A: In order for this decomposition to exist, the linear order $L$ must be compatible with the direction of at least $\frac 23$ of the edges in the graph. (It's compatible with every edge that is its own $H_i$, and with $\frac{m-1}{m} \ge \frac23$ of the edges in each $m$-cycle.)
Many graphs are not going to have such a linear order. For example, take a random tournament on $n$ vertices: for each pair of vertices $\{x,y\}$, add edge $xy$ or $yx$ with equal probability. We can show that with a very high probability, especially as $n \to \infty$, no such linear order exists.
For a fixed linear order $L$, the number of edges of the random tournament compatible with $L$ is a random variable $\mathbf X_L \sim \text{Binomial}(\binom n2, \frac12)$. By a Chernoff bound, taking $\mu = \frac12 \binom n2$ and $\delta = \frac13$,
$$
   \Pr[\mathbf X_L >\tfrac23 \tbinom n2] < e^{-\delta^2 \mu/(2+\delta)} = e^{-\binom n2/42}.
$$
There are, of course, $n!$ possible linear orders $L$. But the probability that $\mathbf X_L$ exceeds $\frac23 \binom n2$ for any of them is still at most $n! \cdot e^{-\binom n2/42}$, which is still tiny: $n! < n^n = e^{n \log n}$, and $n \log n$ loses to $\binom n2/42$.
In general, we're going to get a similar result for a random directed graph with $m$ edges: $\Pr[\mathbf X_L > \tfrac23 m] < e^{-m/42}$. So almost all graphs with more than $\Omega(n \log n)$ edges will not work.
